把“蓝桥杯”“DFS”这两个词放到一块意味着你大概率已经走过了语法入门、暴力枚举阶段开始进入算法题里最容易“一学就会、一写就错”的深搜环节。第五天是一个很微妙的时间节点前四天你多半已经刷过递归、排序和基础模拟对STL的vector、string、sort这些工具足够熟悉而后面的动态规划、图论正等着你。这时候用一整天集中啃DFS性价比其实很高——DFS本身是搜索题的核心又是递归进阶、记忆化搜索、拓扑遍历、状态压缩的“前置技能树”把DFS啃透后面学DP时你会发现很多直觉是相通的。这篇文章的目的很直接把蓝桥杯比赛里DFS的考察点、暴力拿分策略、剪枝思路、常见翻车原因一次性捋清楚并给出可以直接跟着敲的模板和当天的题单安排。不管是C组还是Python组不管是省一目标还是国赛冲刺这天的内容都值得认真走一遍。1. 第五天冲刺DFS考情视角的“值得”与“不值得”1.1 蓝桥杯里DFS到底考什么蓝桥杯的DFS题说“遍地开花”不算夸张。填空题里经典的“方格分割”“牌型种数”“凑算式”编程大题里的“迷宫”“连通块”“拨开云雾见天明”本质上都是深搜或深搜的变体。省赛B组和A组的历年真题里DFS相关的题目通常占2~3道分数占比可能在20~40分之间。国赛阶段DFS还会和DP、状压、剪枝组合出综合题难度直接上一个台阶。但这并不意味着你要把DFS当成“神”来拜。从出题人的角度去看蓝桥杯其实很偏爱“暴力能拿分”的题数据范围卡得不死的时候DFS全排列可以过掉一部分不算大的nDFS配合简单剪枝后常常能从超时边缘拉回到可接受范围。换句话说DFS是一个“保底手段”也是很多难题的兜底策略。1.2 为什么第五天需要专门“盘”一遍DFS前面四天如果只在搞基础语法和简单枚举那你可能还没真正理解“递归函数栈”的展开过程如果已经刷了一点DFS但每次写完总差那么几个剪枝那更需要系统梳理。第五天做DFS专项目的不是刷题量而是建立稳定的“深搜思维模板”。我见过不少同学DFS代码能默写但一到考场就出问题要么不知道什么时候该回溯要么访问状态没还原要么数据一大直接栈溢出。归根结底是脑子里没有一套“什么时候进入下一层、什么时候恢复现场、什么时候剪枝”的判断框架。这一天的核心任务就是把这套框架固化下来。还有一个现实原因蓝桥杯省赛时间紧四道编程大题连做带调中间没有太多时间给你“现场推倒重想”。如果DFS模板能直接秒套省下来的时间可以留给后面的DP题目。所以今天的内容不是教你新鲜概念而是把高频模式压缩成可以直接调用的“肌肉记忆”。2. DFS的底层框架递归树、参数设计与回溯三件套2.1 深搜到底在搜什么DFS的全称是Depth First Search深搜。它做的事情本质上是“沿着一条路走到黑走不通就回头换下一条”。这句话听起来简单但代码里要落地核心是靠“递归函数里的参数”和“当前状态的修改/恢复”配合完成。想象你在走迷宫每到一个岔路口先选择第一个方向走到尽头如果尽头是死路就退回岔路口再挑下一个方向。计算机里的“退回来”就是函数返回后把之前改过的状态变量还原到进入递归前的样子。这也是为什么DFS老手都会反复强调“回溯时恢复现场”。如果你写的是二叉树遍历那种不需要恢复的递归那叫“先序遍历”一旦涉及棋盘、排列、路径、连通块基本都要和“状态标记”打交道。举个例子全排列问题求{1,2,3}的所有排列vectorint path; bool used[10]; void dfs(int n, int depth) { if (depth n) { // 输出path return; } for (int i 1; i n; i) { if (!used[i]) { used[i] true; path.push_back(i); dfs(n, depth 1); used[i] false; // 恢复现场 path.pop_back(); // 恢复现场 } } }这里的used[i]和path就是“状态变量”。按下一次尝试前标记递归结束后立刻撤销这套操作就是深搜回溯的“三件套”。写得多了你会形成反射凡是在for循环里准备进入下一层先问自己三句话——这个状态改了吗递归回来后需不需要恢复不恢复会不会影响后面的兄弟分支2.2 递归出口怎么写才不容易错递归出口是深搜里最“凭感觉”的部分但蓝桥杯的题基本就两类一是“枚举完所有位置”出口比如全排列的depthn、棋盘填完最后一行二是“找到目标状态”出口比如迷宫出口坐标匹配、通过某种条件判断成功。出口写太早会漏解写太晚会多搜很多无效层。我的习惯是先把出口写在函数最前面再处理剪枝。先判断“当前状态能不能直接得到答案”再判断“还有没有继续搜的必要”。比如数独填充题出口通常是“所有空格填完”因为这时候才真正生成了一个完整棋盘。如果你在填到一半就输出必然出错。出口处还有一个容易丢分的点多组解的去重。有些题目要求“字典序最小”或“升序排列”你在出口拿到一组结果后需要判断顺序。实操中很多人会先在递归里生成全部排列最后用sort统一排序其实完全可以在for循环的起点上做文章——比如固定搜索起点让序列天然按字典序生成。这个技巧在后面组合题里特别实用。2.3 建图方式影响DFS的写法和速度蓝桥杯的DFS题图一般有两种存在形式一种是显式的邻接矩阵或邻接表多出现在图论题里另一种是隐式的网格图或状态图比如迷宫、岛屿、棋盘跳跃。网格题用二维数组存图坐标用(x,y)表示。横向、纵向、对角线的移动提前写好方向数组int dx[] {1, -1, 0, 0}; int dy[] {0, 0, 1, -1};然后在DFS里通过for k in 0..3来尝试四个方向。这个方向数组的写法太常用了我建议你直接记成模板。如果要走八个方向就在dx和dy里多加四个对角坐标如果题目里有“马走日”就把马能走的八个目标点写成坐标偏移表。显式图则要关注存图方式对复杂度的影响。n小于20时邻接矩阵扫一遍无所谓但n到1000邻接矩阵每次深搜扫n个点复杂度直接O(n^2)这时要改成邻接表或vector数组。蓝桥杯有些DFS题数据范围不大反而经常能靠“邻接矩阵剪枝”蒙混过关但养成写邻接表的习惯更稳妥。3. 五个高频题型模板、陷阱与蓝桥杯变式3.1 全排列与去重不重不漏才是真难点全排列是DFS的“Hello World”可蓝桥杯不考裸的全排列通常会叠加“去重”或“特定顺序”要求。比如有重复字符的排列、给定n个数按字典序输出不重复的排列这时如果只是用used[]标记某个下标是否用过结果中会出现重复排列。去重方案有两种。排序后在同一层for循环里跳过“和前一个数相同且前一个数没被用过”的情况sort(a.begin(), a.end()); void dfs(int depth) { if (depth n) { ...; return; } for (int i 0; i n; i) { if (used[i]) continue; if (i 0 a[i] a[i-1] !used[i-1]) continue; used[i] true; path.push_back(a[i]); dfs(depth 1); used[i] false; path.pop_back(); } }很多人看不懂!used[i-1]这个条件。其实它的含义是当两个相同数字出现在同一次选择时只允许“前一个先被选”的分支进入搜索后一个相同数字只有在前面那个已经恢复现场时才能进行。这样相同值的排列只会被生成一次。这个细节在“数字方块”“牌型组合”这类真题里反复出现值得死记。3.2 连通块搜索从“数岛屿”到求最大面积连通块问题在蓝桥杯里频率极高典型题是“统计图中1的连通块个数”“求最大连通块面积”“判断某点属于哪个连通块”。这种题DFS和BFS都能做但DFS代码更短面试和比赛里都好写。核心写法遍历每个格子遇到未访问的目标值时进入DFS把所有相邻且同值的格子标记掉同时累加面积、统计周长等。如果把整个二维数组的访问状态用一个vis[][]数组记录那么外层循环每次进入DFS就代表发现了一个新连通块。这里隐藏着一个优化点有些题目允许多次询问同一个点或者要求动态修改格子状态。此时可以提前把所有连通块编号存好建立“格点到连通块编号”的映射。蓝桥杯的规模一般不大临时用DFS现搜也能过但编号映射的方式更稳能避免超时。我实操时经常犯的错是方向数组里漏了某个方向导致连通块被拆成两半。检查方法很简单用一个3x3的小网格手推一遍看周围八个格子是否全覆盖。3.3 回溯经典八皇后、N皇后与棋盘覆盖N皇后是回溯法绕不开的代表题。蓝桥杯不一定直接考八皇后但“在棋盘上放置互不攻击棋子”的变体很多比如“放置k个国王要求互相不能攻击”“骑士巡游”“数独”。N皇后DFS的常见写法是按行搜索。每行放一个皇后检查当前列、主对角线、副对角线是否已有皇后。检查对角线可以用数组下标规律主对角线满足row - col为常数副对角线满足row col为常数。用哈希数组记录这两个值是否占用代码比现场循环检查快得多也不容易错。还有一个值得记的优化对称性剪枝。八皇后问题中第一行皇后的位置如果放在左侧那么右侧对称的解会自动重复。可以在第一行只枚举一半位置最后答案乘2。这种剪枝思路在“棋盘填数”“旋转对称”类题目里能直接减掉接近一半的搜索量。3.4 记忆化搜索带返回值的DFS与DP的暧昧关系记忆化搜索说白了就是把DFS每次算出的结果存下来下次遇到相同状态直接返回不重复递归。它和DP的递推本质相同只是思考方向不同。蓝桥杯的线性DP、区间DP题目很多都能先用带返回值的DFS写出来再顺手加个memo数组。典型例子是最长递增路径int memo[105][105]; int dfs(int x, int y) { if (memo[x][y] ! -1) return memo[x][y]; int best 1; for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (a[nx][ny] a[x][y]) { best max(best, dfs(nx, ny) 1); } } return memo[x][y] best; }注意这里DFS返回的是最佳路径长度不再只是“探索”。写这种题时要搞清楚状态参数哪些影响结果哪些不影响。如果两个不同的搜索路径到达同一个(x,y)后续结果完全一样就可以用memo复用。判断错误会导致答案偏小或偏差属于比较隐蔽的bug。从蓝桥杯应试角度看记忆化搜索最大的价值在于你在考场上推不出递推方程时可以先用暴力DFS加memo“骗”到正确结果只要整体复杂度能接受照样拿分。所以最后一个月的冲刺一定要把这种写法练熟它是暴力分和满分之间的缓冲地带。4. 剪枝策略决定DFS是AC还是TLE的分水岭4.1 剪枝的三种常见姿势剪枝不是“优化技巧”而是DFS题目的灵魂。同样一道题不剪枝可能枚举10^12种状态剪几刀后只剩10^5差距是天上地下。按我的经验蓝桥杯常用的剪枝有三种可行性剪枝当前状态明显不合法直接return。比如N皇后里当前列已经有皇后不需要往下搜数独里填入的数字与行、列、宫冲突直接跳过。最优性剪枝当题目要求最短步数、最少花费时如果当前步数已经超过已知最优解后面再怎么走都不可能更好直接return。冗余性剪枝对结果无影响的对称、平移、首元素固定等提前排除重复分支。全排列固定第一个数就是典型的冗余性剪枝。有一个容易被忽略的坑剪枝条件写错会把正确解也剪掉。建议每加一个剪枝先用小样例验证再跑一次暴力对比。不要一上来就“大胆剪枝”剪出bug后调试的时间反而更多。4.2 估值与边界提前算一算剩余最乐观情况“乐观估计”是竞赛圈常说的A*思想在DFS里的简化版。比如走迷宫求最短步数时可以用曼哈顿距离作为剩余步数的下界当前已走步数 剩余位置到终点的曼哈顿距离如果已经大于已知最优解那直接放弃这条路。蓝桥杯题里不一定要求这样精细的估值但“贪心地提前算一算剩余可选数量”有时候很管用。比如求“从n个数里选k个和小于某个上限”时可以先把数组排序如果当前和加上剩余最大的几个数还达不到目标或者加上最小几个数已经超限都可以剪掉。这种剪枝虽然不能保证最坏情况但在随机数据下往往能砍掉大量分支。考场时间有限优先写“简单且不会剪错”的剪枝比如排序后的边界判断而不是花半小时设计复杂的启发式函数。4.3 迭代加深DFS的进阶保命手段有些搜索树深到离谱但答案其实在很浅的层里。这时候用纯DFS可能一头扎进死胡同用BFS又可能内存爆炸迭代加深IDDFS就是折中方案控制递归深度逐层加深每层都跑一遍DFS。蓝桥杯国赛偶尔会出现这种题比如“埃及分数”“倒水问题”。写迭代加深的模板不复杂for (int depth 1; depth maxDepth; depth) { if (dfs(0, depth)) break; }关键点是在DFS里加入if (curDepth limit) return;的深度限制。这样做能保证每次搜索都控制在一定深度内同时具备DFS的空间优势和BFS的最短路径特性。如果时间紧张可以先把正常DFS写出来再在外面套一层深度限制当数据很大时用它来兜底。5. 蓝桥杯真题实战思路三道典型题型拆解5.1 迷宫类题目坐标DFS最优解剪枝迷宫题大概是蓝桥杯出镜率最高的DFS场景之一。核心解法无外乎从起点出发向四个方向深搜遇到障碍返回访问过的格子标记掉如果求最短路径则在到达终点时更新答案并配合最优性剪枝。这里要特别小心一个细节有些迷宫题需要“走一步标记回溯后恢复”因为不同路径可能经过同一个点有些题则是“每个点只能走一次”标记后不需要恢复。这两种场景的区别直接决定你要不要执行vis[x][y] false把两者搞混是最高频的翻车原因。求“最短路径”时我建议先用BFS保证正确性再用DFS做剪枝对比。因为BFS天然按层扩展第一次到终点就是最短DFS则要在整棵搜索树里遍历必须有良好的上下界剪枝才勉强不超时。如果题目数据量在20x20以内DFS配上dist[x][y]数组做剪枝也够用但千万别在没有剪枝的情况下硬跑大网格。5.2 方格分割、牌型组合类题目对称与哈希去重蓝桥杯省赛填空题里出现过“方格分割”这类题求把一个n×n方格分成两个完全相同的部分有多少种方案。这种题的难点不是深搜本身而是去重旋转、翻转、镜像后的方案都算同一种直接枚举会重复计数。常规解法是利用对称性只用搜索一半格子另一半通过对称坐标自动补全最后把中心轴对称考虑进去。具体实现时经常从中心点出发进行DFS访问一个格子就把它的对称格子也标记掉。出口是边界位置最终统计时要除以旋转对称的次数。这类题没有固定模板非常考验对“等价状态”的理解。考场上遇到这种题心态要稳。如果你真的分析不清楚对称性最保守的办法是枚举所有分割方案再用“哈希集合”存储对每种方案生成它的所有对称形式如果集合里已经有其中任何一种就跳过。这个方法慢但不容易错对填空题小数据来说足够拿分。5.3 全排列枚举条件判断暴力拿分的快乐很多蓝桥杯编程大题尤其是数据范围在n10的题本质就是全排列穷举。比如“数字拼接成最大整数”“排列后判断是否能整除”“n个数的运算符插入”。这类题不需要高端优化只要写出标准全排列框架在出口处判断条件即可。我的建议是如果题目里n不大先别急着想数学规律直接DFS全排列暴力。蓝桥杯的判题数据里n小这种情况非常常见。很多“原创题”其实就是把DFS包装得花里胡哨背后的搜索树节点数并不多。暴力能拿70%的分剩下的再想优化也来得及。验证全排列DFS是否正确有个实用技巧找一个n3或n4的小数据手算预期结果然后让程序输出所有排列看看数量和字典序是否符合预期。这一步能排查掉大部分“used标记不全”“回溯遗漏”问题。6. 常见错误、调试方法以及赛场上的“急救”技巧6.1 五个最容易让蓝桥杯选手翻车的深搜Bug回溯遗漏递归返回前忘了恢复used、vis、path等状态导致后续分支“脏状态”蔓延。调试时留意输出结果中的异常重复和缺失。递归出口顺序错误把出口写在剪枝之后导致某些状态提前被剪掉输出少解。重复搜索同一状态比如在网格图中方向数组写错导致在两个格子之间反复徘徊。解决方法是加一个step限制或记录前一个坐标。数组越界高维数组下标没检查尤其是对角线数组row - col n忘了加偏移量直接访问负下标。栈溢出递归深度超过几万层时程序会直接运行错误或崩溃。蓝桥杯线上环境里注意把main函数改成显式栈、减小递归层数或改用BFS。6.2 用“打印递归树”的办法快速定位逻辑错误我调试DFS题有一个非常朴素但屡试不爽的土办法在函数开头打印depth和当前状态肉眼观察递归树的展开顺序。数据量小时打印出来的内容能直接告诉你搜索顺序是否符合预期哪个分支被错误剪掉哪个状态没恢复。调试示例void dfs(int depth, int sum) { cout string(depth*2, ) depth depth sum sum endl; ... }打印时用string(depth*2, )缩进能把递归树“画”出来。如果显示器里看到某个分支突然消失多半是剪枝条件写错如果某个状态带着“残留标记”进入下一层能看到重复或错位。定位后删掉打印语句即可。这个方法在比赛里也能用但要记得用cerr而不是cout并且正式提交前注释掉。6.3 考场上的时间分配与暴力兜底原则蓝桥杯省赛的考试时间一般是四小时。我的个人建议看到一道题如果第一眼想到DFS先估一下数据范围。n10直接全排列n20可以考虑状态压缩或DFS剪枝n100多半需要对搜索做记忆化或改用DP。不要在单个题上死磕如果DFS写了20分钟还没跑通先跳到下一题回头再用暴力拿基础分。另一个考场技巧是先写一个不优化的DFS保证能出正确答案再逐步加剪枝。很多同学一上来就开始“高性能剪枝”结果剪枝有bug连基础分都丢了。先暴力、后剪枝、最后一小时统一优化是稳妥策略。即使在国赛这种“由正确到高效”的顺序也远比“上来就追求最优”靠谱。7. 第五天冲刺实操清单与个人经验总结如果今天只有一天时间我会建议你按下面这个顺序练手写一遍全排列、组合、子集的DFS模板并各运行一次确认输出数量正确。刷2~3道连通块题把方向数组、vis标记、面积统计练熟。刷2~3道回溯题重点是N皇后或数独掌握“状态恢复”和“对角线标记”。刷2~3道剪枝题体验从超时到AC的完整过程。留一小时做一套真题里的DFS部分模拟考场时间。题单不用贪多一天能高质量完成十道题已经不错。重点不是“量”而是每道题都能回答三个问题搜索状态是什么出口怎么判断剪枝依据是什么就我个人经历来说DFS是蓝桥杯冲刺阶段“性价比”最高的板块之一。它的入门门槛低但天花板很高——从暴力穷举一路延伸到记忆化搜索、迭代加深、启发式剪枝整个知识链几乎覆盖了搜索题的全部考点。第五天专门花一整天来盘它后面学DP、图论时会觉得思路顺畅很多。尤其到考前模拟阶段看到新题时能条件反射地画出递归树这种“肌肉记忆”就是这天的收获。