距离省考没剩几天了。如果你刷到了这篇说明你正处在这场拉锯战最磨人的冲刺段。我是从大二开始连续两年打蓝桥杯的老选手C/C组拿过省一也在赛场上亲眼见过不少同学在DFS这个板块上翻车。今天是我们这个冲刺系列的第五天前四天咱们把基础语法、STL容器、枚举模拟和排序这些相对友好的内容过了一遍今天要啃的是DFS深度优先搜索。为什么单把DFS拎出来单独练一天因为它是蓝桥杯搜索题的绝对主力。省赛题目里暴力枚举、排列组合、连通块、迷宫、状态搜索几乎全部围绕DFS展开尤其C/C组和Java组DFS几乎是“保省三冲省二”的核心分水岭。Python组和嵌入式组的客观题也会涉及递归思想和图搜索的基础概念。说白了DFS写不写得快、写得稳直接决定你填空题能不能拿满分、编程大题能不能多过几个测试点。这篇文章我只讲三件事DFS到底怎么想、蓝桥杯里DFS最喜欢考哪几类题、以及你在赛场上最容易因为DFS丢掉的分数都丢在哪。全程用备赛视角来讲每段都尽量给可以直接抄的代码和判断标准不讨论过于偏门的优化适合所有还在DFS门口徘徊的选手。如果今天你能把文章里的模板和坑看完再亲手敲两遍我就觉得这个第五天过得值了。1. DFS做题框架先画递归树再写代码1.1 写DFS之前先搞清楚它在做什么很多人一上来就背递归模板结果题目稍微换了个壳子就不知道从哪下手。我建议你换一种理解方式DFS本质上是在枚举一棵“决策树”的所有路径。举个例子。假设你要从数字1、2、3里选两个数组成排列这个“选择过程”其实是分层展开的。第一层你决定第一个数放谁有3种选择第二层你决定第二个数放谁在第一个数已经确定的前提下有2种选择。把这6条路径全部画出来就是一棵递归树。DFS就是从一个根节点出发沿着一条路走到头走不动了再退回上一个岔路口尝试下一条路。这个“走到头再回头”的过程就是递归函数天然适合的原因。因为递归调用本质上是把当前状态压栈等子问题处理完了再弹栈恢复现场。你不用手动维护一个栈就能实现回溯。这也是DFS和BFS最大的区别DFS用递归代码短BFS用队列逻辑直观但代码长。蓝桥杯里求“所有方案”“是否存在解”的题目DFS是首选。在实际写代码之前我的习惯是在草稿纸上画出递归树的至少两层明确每一层在做什么选择、有多少种分支、什么时候到达叶子节点。这步不需要花费太多时间但能极大减少写错递归出口的概率。你别觉得画图浪费时间赛场上最怕的不是题目难而是代码越改越乱最后连自己写的逻辑都看不清。1.2 一个万能的DFS骨架这里给你一个蓝桥杯考场通用的DFS函数骨架。往上套题90%的DFS题都能过。void dfs(int step) { // 1. 递归出口达到目标状态记录答案或更新最值 if (step n) { // 处理得到的方案 return; } // 2. 枚举当前层所有可能的选择 for (int i 0; i n; i) { if (!used[i]) { // 如果这个选择未被占用 ans[step] i; // 记录当前选择 used[i] true; // 标记占用 dfs(step 1); // 递归进入下一层 used[i] false; // 回溯取消标记恢复现场 } } }这个模板里最核心的是三部分递归出口、循环枚举、恢复现场。其中恢复现场这一步就是used[i] false是新手最容易丢的。很多人不明白为什么要“恢复现场”。我打个比方你在迷宫里走每走过一个岔路口就在地上放一个标记防止下次再来。但你如果从某条死路退回来了必须把刚才放的标记收掉否则下次从另一条路进到同一个岔路口时会误以为这条路已经走过从而漏掉正确路径。DFS里的used[i] true相当于放标记used[i] false相当于收标记。只放不收搜索结果必然出错。还有一类DFS不需要恢复现场比如“每个节点只能访问一次且求连通块数量”的题。但作为新手我强烈建议你统一用“先标记、递归、后取消”的写法等你能判断清楚一道题到底要不要恢复现场再按需删掉这一步也不迟。2. 蓝桥杯DFS四大高频场景与对应模板2.1 排列、组合、子集DFS的地基题蓝桥杯历届省赛里排列组合类题目出镜率极高。直接考全排列的年份不少更多时候是把排列组合嵌在枚举方案里比如“从n个数中选m个数求和问和有多少种不同值”“8皇后问题”“给迷宫里的格子编号求路径方案数”等。这类题就是上面那个骨架的变体。区别主要在于两层循环的起点和“选择”的定义不同全排列每层从第一个元素开始枚举用used[]避免重复选中同一个元素。组合每层从start 1开始枚举保证后面的数永远比前面的大避免出现(1,2)和(2,1)这种重复组合。子集对于每个元素有“选”和“不选”两条路递归分叉为两个方向。组合问题里那个“start”参数很多人写不对。它的作用是控制枚举范围保证不回头选前面的数。假设现在要从 {1,2,3,4} 里选两个数第二层如果从下标0开始枚举就会出现选过1再选1的情况或者出现(1,2)和(2,1)同时出现。加一个start参数让第二层永远从上一层选的数后面开始枚举组合数就自动去重了。// 选出 m 个数每个组合只保留升序 void dfs(int start, int cnt) { if (cnt m) { // 输出 ans 数组 return; } for (int i start; i n; i) { ans[cnt] i; dfs(i 1, cnt 1); } }这段代码里根本没有used[]数组为什么不会重复因为start 1保证了下一次只会选更大的数。这就是组合和排列写法上的本质区别。2.2 网格类连通块问题染色法DFS蓝桥杯特别喜欢考二维网格上的DFS比如“数一数有多少片水域”“判断岛屿面积最大是多少”“地图染色最少用几种颜色”。这类题型的特征是给你的数据是二维矩阵每个格子有状态陆地/水域、可走/不可走需要你统计连续区域或大小。模板也是统一的。每个格子作为一个起点进入DFS后把当前格子标记成“已访问”再向上下左右四个方向递归。void dfs(int x, int y) { if (x 0 || x n || y 0 || y m) return; // 出界 if (vis[x][y] || grid[x][y] 0) return; // 已访问或不可走 vis[x][y] true; cnt; // 统计连通块大小 dfs(x 1, y); dfs(x - 1, y); dfs(x, y 1); dfs(x, y - 1); }注意这里的vis[x][y] true不需要恢复现场。因为连通块问题中一个格子只要被统计过一次永远不需要被第二个连通块重复统计。如果你在这个模板里加上“回溯取消标记”反而会让格子被重复统计多次计数直接翻倍。判断“要不要恢复现场”有一个很简单的标准如果搜索的目标是找一条路径、求一组排列方案每条路线的选择会影响其他路线必须恢复现场如果搜索的目标是给所有点划分集合、统计每个点属于哪个区域不需要恢复现场。把这句话想明白你至少能避开一半的DFS错误。二维DFS里还有一个常见需求是求连通块中“坐标的极值”比如“求连通块上下左右边界围成的面积”。做法是在DFS里同时维护minX, maxX, minY, maxY四个变量。这个技巧在很多图形切割题里用到建议你动手敲一遍熟悉在DFS参数列表里传递成员变量的写法。2.3 迷宫路径搜索DFS/BFS怎么选迷宫寻路题是蓝桥杯经典中的经典。省赛里出现过“问从起点到终点有多少种走法”“给定障碍物问是否存在路径”“走出迷宫最少需要多少步”等不同问法。这里有一个特别重要的判断依据如果题目问“有多少条可行路径”或“是否存在一条可行路径”用DFS。因为DFS会遍历所有可能的分支天然适合统计方案数。如果题目问“最短路径是几步”别用DFS改用BFS。DFS求最短路径不是不行但它需要“走到终点后更新最小值再回溯继续搜”最坏情况下会把所有路径全走一遍指数级复杂度会让你直接超时。BFS的模板我用文字描述一下用队列保存当前层的所有节点每次从队首取出一个节点扩展相邻节点并记录步数第一次到达终点时的步数就是最短路径。逻辑简单代码量和DFS差不多但在求最短路的场景下效率天差地别。2026年C/C组真题里有一道类似“迷宫传送门”的题其实质就是在DFS基础上增加了“两种移动方式”的分支。这种题并不难关键是有没有意识到把新增的移动方式也放进DFS的分支枚举里。很多同学卡住是因为把思维锁死在上下左右四个方向上忘了传送门也是一种“走法”。DFS写迷宫题时还有一个极易出错的点起点的标记时机。如果你在进入DFS之前就把起点标记为已访问而不是在DFS函数体内标记那么别的路径就无法再经过起点。某些题目允许路径重复经过起点虽然少见时这种写法就会漏解。我建议统一在函数体入口处标记思路更清晰。2.4 剪枝让DFS从“超时”到“刚好能过”蓝桥杯省赛的DFS题数据范围一般不会太大但偶尔也会出现不剪枝就只能过一半测试点的情况。剪枝说白了就是提前判断某条分支不可能得到合法答案直接跳过这条分支不再递归。常见的三种剪枝策略按代码代价从低到高第一是边界剪枝。比如“当前已经用了k个数剩下的数全选上也无法到达目标值”直接return。这是最简单也最有效的剪枝在求和类题目里尤其明显。第二是奇偶剪枝针对迷宫题。假设从 (x1,y1) 到 (x2,y2) 的曼哈顿距离是d当前已经走了step步剩余步数为 t如果(t - d) % 2 ! 0直接return。因为每一步走相邻格子都会改变坐标的奇偶性奇偶不匹配说明无论如何都不可能按时到达。这个技巧在“能否在限定步数内到达终点”的题里几乎是万能解法。第三是最优性剪枝用于最值类问题。如果DFS过程中已经拿到的“当前最优值”比“当前路径的下界”还要好剩下的搜索就不需要继续了。比如求“把n个数分成两组使两组和之差最小”这种题一旦当前差值已经大于已经搜到的最优值直接剪掉。剪枝的本质是用逻辑判断换递归时间。别追求把所有剪枝都写全能想清楚一种关键剪枝往往就足以让你从TLE变成AC。3. 新手最容易踩的五个DFS深坑3.1 恢复现场与访问标记到底该在哪写前面已经提过恢复现场但这个问题实在太关键值得再展开一次。排排列组合题中恢复现场是必须的否则一个排列里的元素会被后面所有的排列“共用”产生重复和遗漏。我见过最典型的错误写法是递归出口里输出方案后忘了回溯used[i] false。结果就是只输出了一个排列后面的方案全被拦截。网格连通块题中vis一旦标记就不再取消。如果你把排列题的模板原封不动搬过来很可能会在dfs函数结尾加一行vis[x][y] false。看起来没有什么问题实际会让同一个格子被多个连通块重复计算。我的建议是写完DFS函数之后先盯着函数尾部的三行代码问自己这一层选择的影响需不需要传递给下一次兄弟递归如果需要就恢复现场如果不需要就不恢复。想不清楚的时候宁可不去恢复也不要盲目恢复。因为漏恢复导致的错误通常能在样例测试中发现而错恢复导致的错误往往十分隐蔽你可能调半小时都找不出问题。3.2 递归深度太深栈溢出怎么办蓝桥杯评测环境下的递归深度通常受系统栈大小限制。如果你在二维矩阵上做DFS棋盘行列数达到1000x1000时万一递归走到整张图的最长路径很容易爆栈。解决方式通常有两种。第一种是改写成“手动栈版DFS”用vector模拟栈来存储待访问节点。这种写法不依赖系统递归栈但代码逻辑稍复杂平时练习少的话不建议赛场上临时使用。第二种是优化递归路径尽量在递归之前剪掉明显不可能的方向减少递归深度。实操中最实用的调节方法是使用std::ios::sync_with_stdio(false)加速输入输出再在代码开头尝试定义局部数组时减小空间占用。递归爆栈有时候不是因为递归本身多深而是系统栈剩余空间被大数组占用过多用全局数组代替局部大数组往往就能解决。3.3 多组测试数据忘记清空状态蓝桥杯编程题绝大多数是多组测试用例每组数据都要独立计算答案。而DFS里用的vis[]数组、计数器cnt、答案容器ans都是在上一组数据中残留的。如果你在每组数据开头没有重新初始化就会出现“上组数据影响下组答案”的灵异问题。我自己就吃过这个亏。当年写一道连通块题目样例全过提交只对了一半测试点。调试了一个小时才发现是vis数组没有在下组数据开始时memset上一张地图的访问标记全带到了新地图上。后来我养成了一个习惯所有涉及多组输入的DFS题读入数据后第一时间清理状态再开始搜索。具体做法是在while (cin n)循环体内每次读入完矩阵后立刻做memset(vis, 0, sizeof(vis));。如果是用vector存储答案也记得clear()一下。别小看这一步省赛里因为这种低级失误丢分的选手大有人在。3.4 在递归里修改全局变量的顺序问题DFS函数里经常写这样的逻辑进入某个分支时ans[step] value递归返回后再恢复现场。如果ans是全局变量你必须在修改它的同时保证不会影响到其他分支的赋值。这听起来像是废话但实际写起来总有错误。举例全排列的ans数组在下一次递归之前会被覆盖。如果你是在递归出口才把ans的内容输出或存入结果集那没问题。但如果你在递归过程中就基于ans做了判断比如判断相邻两个数的差值是否满足某种条件这时候ans中尚未赋值的位置可能会有上一次残留的数据从而干扰判断。解决思路是所有需要基于“当前路径”的判断最好放在递归出口处统一处理如果需要更早判断就用vector保存当前路径每次递归时 push 进去、回溯时 pop 出来不要用固定数组去“覆盖”这样残留数据不会干扰逻辑。3.5 递归出口写成“判断”导致漏解很多人在递归出口里写if (step n)这没有问题。但也有题目要求“只要满足某个条件就停止”比如“找到一组解就输出并终止全部递归”。这种场景下使用if (找到) return;但要注意这个return只会退出当前层如果外层还有循环仍然会继续搜索。要“终止全部递归”单纯靠return是不够的。需要加一个全局标志位bool found false;在每一层判断if (found) return;。或者在递归出口处直接抛出异常不推荐影响可读性。我在往年蓝桥杯模拟赛里见过一道“九宫格填数求唯一解”的题很多同学就是这里卡住找到解后又继续跑了几万条无意义分支白白超时。其实更好的思路是先想清楚“输出全部分支”还是“只输出第一组解”然后对应调整DFS写法。“只输出第一组解”可以用found标志位也可以用把出口返回值设计成bool的方式一旦子问题返回true父层立即return true。这个方法写起来很优雅但前提是你要理解DFS的返回值会逐层向上传递。4. 冲刺期DFS的题型优先级与拿分策略4.1 按投入产出比给DFS题排序离省赛没几天了你不可能把所有DFS题型都刷到满分。我建议按下面的优先级分配时间可以说是我自己刷题经验的总结。第一优先排列组合与子集。这是DFS板块中代码最短、最容易写对、出题频率又最高的题型。填空题里只要碰到“有多少种排列/组合/方案”直接套模板就能拿分。建议把全排列、组合、子集三种模板各敲3遍做到不假思索写出来。第二优先二维网格连通块。这种题代码量稍长但模板固定。只要记得vis不回溯基本就是循环嵌套DFS。省赛题里经常作为编程大题的第一问出现拿下这10-16分非常划算。第三优先带剪枝的搜索。这类题才是真正拉开差距的地方。会写剪枝你就能从一个测试点都过不了的TLE变成至少通过一半测试点的稳定得分。但剪枝需要一定训练量切记不要在赛场上临时发明剪枝公式平时练习时就整理好一套自己的剪枝模板。第四优先状态压缩和记忆化搜索。这种题在省赛里属于拔高题通常出现在压轴位置对新手来说性价比不高。能看懂题解就好不必花大量时间死磕。题型优先级这个东西说到底要跟你的省赛目标匹配。目标是省三前两类足够目标是省一第三类必须拿下。别总想着一步登天最后几天把能拿的分拿稳比挑战压轴题重要得多。4.2 赛场上的时间分配和“暴力分”策略蓝桥杯省赛的编程大题一般是多测试数据点计分过了一个点算一个点。这意味着即使你只会写一个“暴力DFS”只要数据范围小也能过一小半测试点。这一点特别重要因为很多同学一看题目太难直接空着一分拿不到。正确的做法是哪怕只有DFS一个思路先写上保底分再在这个基础上去剪枝优化。我的实战建议是竞赛开始后先把所有题目都读一遍花5分钟判断每道题是不是DFS题并且预估自己能不能写出来。然后从填空题开始做因为填空没有过程分对了就是全对。接着做有把握的中等编程题每道题控制在30分钟以内。最后留给最难的压轴题15分钟能写多少写多少写上暴力DFS至少能捞到一个测试点的分。如果你做了计划外的事比如某道题半天没思路我的经验是直接放弃纠缠跳到下一题回头再来看。DFS题往往需要一点“灵光闪现”你盯着它看半小时想不出来的东西隔一段时间再看反而能看穿。4.3 最后几天刷真题的三个方法刷真题的目的不是“遇见原题”而是建立题型直觉。哪道题用DFS、哪道题用BFS、哪道题要回溯、哪道题不回溯这些判断在做题过程中会慢慢形成肌肉记忆。第一个方法按专题刷。把近五年的蓝桥杯省赛C/C组真题里所有DFS相关题挑出来集中做一遍。不要一道一道跳着做集中轰炸同一题型更容易形成模板。第二个方法限制时间做题。每道题给自己设定30分钟30分钟内没写出来就看题解然后合上答案自己重写一遍。这个过程模拟比赛压力比无脑刷几十道题更接近真实赛场。第三个方法做错的题必须三刷。当天错一遍隔一天再独立写一遍过一周再写一遍。DFS题的错误点往往集中在回溯和剪枝多写几遍自然就记住了。别迷信所谓“押题”。蓝桥杯的出题风格逐年变化但DFS作为一个算法思想不管题目怎么包装核心思路永远是那棵树、那三个要素。把模板吃透以不变应万变是最稳的。4.4 调试DFS的两个利器最后分享两个我自己调试DFS特别喜欢用的方法。第一个是打印法。在递归函数的第一行输出当前的step和路径状态能直观看到程序在按什么顺序搜索。很多“怎么少了一种方案”的问题一打印就能看到是某条分支没进或者是某条分支提前退出了。第二个方法是小数据测试法。直接构造一个n等于3或4的最简数据手工列出所有可能方案然后用程序跑一遍对比数量是否一致。这比用大样本测试高效得多。比如全排列n等于4时有24种方案如果程序输出只有12种说明你的某个分支被错误地拦截了这时再想是used数组初始化问题还是递归出口问题范围就小得多。还有一个容易忽略的经验先把DFS写成“不必要的功能都砍掉”的简版确认逻辑正确后再逐步添加功能。我见过太多同学一上来就写完整版里面既有最优性剪枝又有路径记录又有状态压缩出错后根本不知道问题在哪。先跑通原始DFS再一层层加这个顺序永远不会错。写在最后我今天把这五天的内容串起来看了一下发现DFS这关其实是蓝桥杯省赛里“付出立刻有回报”的板块。它的模板固定、题型清晰练一道就真的会一道远比那些需要大量数学功底的题目友好。我自己当年的经验是把全排列和连通块两个模板敲到闭眼能写再配合基础的剪枝思路省赛的搜索题基本就不会拉胯。最后再分享一个小技巧。等你们上了考场如果真碰上DFS题卡壳不要慌先在草稿纸上写一个小的递归示例盯住两件事第一递归出口到底什么时候触发第二每层的选择分支有没有被访问数组正确地控制。这两点想通了DFS的难关也就过了大半。今天这一篇是冲刺系列里最长也最硬核的一篇希望你能静下心来把代码模板实操一遍。离比赛还有时间稳住节奏每天都能比昨天更稳一点。省赛加油。