今天是冲刺蓝桥杯打卡的第四天。前三天我把递归基础、回溯框架和常见模板题过了一遍今晚准备把DFS板块整体收尾。说句实话DFS这块内容真学透了蓝桥杯省赛至少能拿到两成以上的分——不管是填空里的排列组合题还是编程大题里的地图遍历、路径计数、模拟枚举DFS都是最常见的切入方式。这篇文章就当作我今晚的复习笔记从底层递归逻辑到真题模型再到踩坑记录完整梳理一遍也给我后面十几天的刷题留个索引。先说清楚读者定位如果你已经会写基本的递归函数但对DFS的边界条件、恢复现场、剪枝时机还比较模糊或者你刷了不少题但总在某个环节超时、重复、漏解那这篇文章应该能帮上忙。如果你完全是零基础建议先找一套全排列模板题跑通再回来看效果会好很多。1. 为什么第四天还在死磕DFS蓝桥杯里的考察密度与复习策略先看蓝桥杯省赛的题目结构一共10道题5道填空、5道编程覆盖枚举、模拟、贪心、动态规划、搜索、数论等方向。其中DFS/BFS是搜索类问题的绝对主力几乎每年都有至少一道编程大题直接考搜索填空题里也经常出现能排列多少种方案有多少种走法这类需要用DFS枚举的题目。我统计了近五年的真题分布大致是这样的场景年份/组别典型题目方向搜索类型省赛B组迷宫走法计数、连通块判断DFS为主省赛A组牌型组合、图形分割DFS枚举剪枝国赛C组状态模拟路径枚举DFS或其他搜索省赛Python组岛屿数量、路径可达性DFS/BFS均可当然这个表只是我个人刷题后的归纳不是官方统计但趋势很明显DFS在蓝桥杯里的考察密度远高于动态规划以外的大部分算法。原因也好理解DFS代码量小、思路直观适合出成中等偏难的题既能考察递归功底又能通过剪枝拉开区分度。第四天我的复习策略和前三天不一样了。前三天是见模板就抄见题就套今天开始必须做三件事第一把DFS的递归框架拆到不能再细确保每一行代码为什么写在那里都能解释清楚第二把真题按类型重新做一遍不是为AC而AC而是总结每类题的固定套路第三专门记录自己写错的地方把赛场上的致命坑提前踩一遍。复习顺序上我建议还没开始的人也按这个节奏来全排列/组合类找感觉→ 地图连通块类练框架→ 路径枚举类练剪枝→ 模拟类搜索练状态设计。这个顺序由浅入深每一类都在上一层基础上加一点复杂度比直接刷真题效率高很多。2. 递归往下钻的三个关键点基线、状态传递与恢复现场DFS的本质是深度优先搜索但在竞赛里你很少真的去手写栈模拟递归绝大多数情况用一个递归函数就够了。很多同学写DFS卡住不是不知道深度优先是什么意思而是对递归函数本身缺少掌控感。我把它拆成三个必须想清楚的问题。2.1 基线条件什么时候停止往下钻基线条件写不好有两种典型表现一种是死循环递归永远不返回另一种是多算了一层答案重复或漏算。判断基线条件的标准只有一个当你的状态已经不需要再做任何选择时就应该返回。比如全排列问题你排列的长度已经达到n就记录答案并返回连通块问题当前位置已经访问过就返回。这里有个小技巧把基线条件写在函数最前面而且要先判断无效/越界情况再判断完成/终止情况避免数组越界后还继续访问。void dfs(int step) { // 基线1非法状态立刻返回 if (step n) return; // 基线2达到目标状态记录并返回 if (step n) { ans; return; } // 继续递归... }2.2 状态传递参数怎么设计最不容易错这是我觉得新手和熟练选手差距最大的地方。DFS递归时哪些信息作为函数参数传下去哪些作为全局变量直接决定代码的清晰度。我的原则是会随路径变化的状态作为参数传递不会变化的全局信息作为全局变量或成员变量使用。比如地图的行列数n、m不会变放全局当前搜索到的坐标x、y会变放参数已选择的数字集合会变放参数或全局加撤销都可以。参数还有一个小坑如果你传的是vector、string这类容器按值传递会每次递归都复制一遍数据量稍大就直接超时。正确做法是传引用并在回溯时手动恢复。// 错误示范每次递归都拷贝一份vector耗时爆炸 void dfs(vectorint path) { ... } // 正确示范传引用用完撤销 void dfs(vectorint path) { if (...) { ...; return; } for (int i 0; i n; i) { if (used[i]) continue; used[i] true; path.push_back(i); dfs(path); path.pop_back(); // 恢复现场 used[i] false; // 恢复现场 } }这两个恢复现场的操作是全排列类题目最核心的考点也是最容易漏的地方。我见过不少同学注释写回溯但只撤销了一半导致答案出现大量重复项。2.3 恢复现场判断标准其实很简单很多教程把恢复现场讲得很玄乎实际上可以一句话概括如果这个状态是沿着当前路径累加的递归返回后必须撤销否则会污染其他分支。举个例子地图标记vis[x][y] true如果不恢复那么从一个分支走过的格子另一个分支就再也不能走了——但实际另一条路径完全可能经过同一个格子这时答案就少了。所以连通块类问题中如果是统计连通块个数标记不需要恢复因为每个格子只要被一个连通块访问过就够了但如果是枚举所有从起点到终点的路径标记必须恢复否则路径数量会严重少算。再举个反直觉的例子有些DFS不需要恢复现场。比如从n个数中选k个的组合数你记录的是选了多少个而不是具体选了哪些那么计数器cnt就不需要撤销递归函数里加一层cntk再传下去本来就是不可变的。// 组合类不需要恢复cnt因为每个分支的cnt是独立传入的 void dfs(int idx, int cnt) { if (cnt k) return; if (idx n) { if (cnt k) ans; return; } dfs(idx 1, cnt); // 不选当前元素 dfs(idx 1, cnt 1); // 选当前元素 }这一段是不是恢复现场从代码看没有撤销动作但逻辑上每个分支都有自己的cnt值互不干扰。这个例子说明恢复现场的实质是撤销对共享状态的修改。如果参数是值传递天然独立根本不需要恢复如果参数是引用或全局就必须手动找补回来。3. 三类绕不开的真题模型地图连通块、组合计数、步数模拟刷完基础框架接下来是把模型对号入座。蓝桥杯的搜索题看着千变万化剥开外壳绝大多数落在三个模型里地图连通块类、排列组合计数类、带状态模拟的路径枚举类。下面逐个拆解每类我都给了可以直接参考的代码框架和关键解释。3.1 地图连通块方向数组与访问标记的标准打法连通块类题目的特征是给一张二维地图里面有某种标记比如#代表陆地.代表水要求统计共有多少个连续的标记区域。蓝桥杯里的岛屿数量全球变暖都是这个模型的变体。核心点有两个一是方向数组二是访问标记。#include bits/stdc.h using namespace std; const int N 105; int n, m; char grid[N][N]; bool vis[N][N]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y) { vis[x][y] true; // 标记当前格已访问 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 先判断越界再判断访问状态顺序不能反 if (nx 0 || nx n || ny 0 || ny m) continue; if (vis[nx][ny] || grid[nx][ny] .) continue; dfs(nx, ny); } } int main() { cin n m; for (int i 0; i n; i) cin grid[i]; int cnt 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] # !vis[i][j]) { cnt; dfs(i, j); } } } cout cnt endl; return 0; }为什么这类题DFS比并查集更合适因为DFS代码量更少、思路直观而且在蓝桥杯的评测环境下二维地图规模通常不超过100×100递归栈深度最多一万层完全扛得住。并查集还得额外实现合并函数代码一长就容易写错。这里有个初学者必踩的坑越界判断和访问状态判断的顺序。有人写成if (vis[nx][ny] || grid[nx][ny] . || nx 0 || ...)看起来好像只是顺序不同但如果nx、ny已经越界访问vis[nx][ny]就会导致数组越界轻则答案错乱重则运行时崩溃。正确的顺序永远是先判断坐标合法性再访问数组内容。3.2 组合计数与全排列可行性剪枝的关键用法第二类是计数题典型代表是蓝桥杯省赛真题牌型种数从52张牌中取13张每种点数最多取4张问有多少种组合方式。这题第一反应是13层for循环但那样代码又长又丑而且一旦点数增多就完全不可行。用DFS枚举是标准解法。#include bits/stdc.h using namespace std; int ans 0; // idx表示当前处理到第几种点数1~13cnt表示已选牌数 void dfs(int idx, int cnt) { if (cnt 13) return; // 剪枝1已经超过13张没必要继续 if (idx 13) { if (cnt 13) ans; return; } for (int k 0; k 4; k) { // 当前点数可以选0~4张 dfs(idx 1, cnt k); } } int main() { dfs(1, 0); cout ans endl; return 0; }这题的剪枝非常有代表性。没有cnt 13这个判断递归也会把所有情况跑完但有了它一旦当前牌数超过13整个分支直接砍掉搜索空间大幅缩小。我实测两种写法的时间差在数据变大后非常明显这就是可行性剪枝的价值。再补充一个常见的去重剪枝场景排序后如果当前元素和上一个元素相同且上一个元素没用过就跳过。这个套路在有重复数字的全排列中几乎必用蓝桥杯真题带分数凑算式里也出现过。if (i 0 nums[i] nums[i-1] !used[i-1]) continue;原理是相同数字在不同分支产生的结果完全一样只保留第一个分支就行。这个剪枝属于必考级建议背下来。3.3 步数模拟与赛跑枚举带状态的DFS怎么设计第三类是热搜词里经常一起出现的龟兔赛跑这类题。蓝桥杯确实考过龟兔赛跑预测兔子每跑一定距离可能休息乌龟匀速跑判断谁先到达终点。表面看是模拟题用while循环按时间步进也能做但一旦题目改成兔子可以选择在不同时间点休息有多个策略可选求最优策略枚举就压到DFS头上了。这类题的状态设计逻辑是把当前时间、双方位置、兔子剩余休息时间作为DFS的状态参数把是否到达终点作为基线条件把选择继续跑/选择休息作为分支。伪代码如下void dfs(int time, int rabbitPos, int turtlePos, int restTime) { if (rabbitPos L || turtlePos L) { updateAns(time); return; } // 分支1兔子继续跑 dfs(time 1, rabbitPos rabbitSpeed, turtlePos turtleSpeed, restTime); // 分支2兔子休息如果有休息策略可选 if (restTime 0) { dfs(time 1, rabbitPos, turtlePos turtleSpeed, restTime - 1); } }真正的龟兔赛跑预测题直接用while模拟更简单但很多变体题——比如最短到达时间给定体力值求最优策略——就必须用DFS枚举。练这类题的目的不是死记代码而是学会把时间轴上的决策拆成递归分支这是搜索类题从模板题走向综合题的关键一步。4. 踩坑实录今晚犯过的错和赛场上的命中隐患刷题不踩坑等于白刷。今晚我专门挑了以前容易错的几类情况重新写了一遍把错误过程和修正方式记录下来。这些坑在赛场上遇到任何一个都可能导致整道题心态崩塌提前踩一遍非常值。4.1 状态恢复遗漏全排列重复项的根本原因我之前写过一版全排列代码思路完全正确但输出结果总是多出大量重复排列。排查了很久才发现我在递归前把vis[i] true递归后却忘了vis[i] false。这导致第一次分支走过的数字在后续分支中永远不可用可用的数字集合越变越小最终大量分支只能输出残缺排列。定位方法很简单在小数据量下手工跑把每一步的vis数组状态打出来立刻就能看到该释放的没释放。建议大家从一开始就养成对称书写的习惯——标记和撤销代码挨在一起中间夹递归调用这样只要改一处另一处必然在视线范围内。vis[i] true; // 标记 dfs(step 1, path); vis[i] false; // 撤销与标记对称4.2 边界判断顺序写反数组越界的隐蔽炸弹连通块代码里if (nx 0 || nx n || ny 0 || ny m) continue;必须放在访问grid[nx][ny]之前。我见过不少同学为了少写一行把条件合并成if (!vis[nx][ny] grid[nx][ny] #)看起来没问题但一旦nx-1vis[nx][ny]直接越界。在C里数组越界不会立刻报错它可能读到内存中的随机值导致判断结果随机整个答案时对时错极难排查。我推荐一个调试技巧如果某道题答案时对时错优先怀疑数组越界。把地图往四周各扩一圈用边界值比如0填充再统一从下标1开始读能大幅降低这类问题的发生概率。4.3 剪枝只做了一半数据量一大就超时很多模板题数据量小剪枝写不写都能过。但蓝桥杯的评测数据不会那么温柔特别是组合计数类题目不剪枝的搜索空间是阶乘级别。我之前在做带分数这类题时吃过亏枚举了所有排列再去判断条件结果n稍大就直接TLE。正确做法是在枚举过程中同步剪枝。比如带分数可以在排列还没排完时就判断当前数字是否已超过n的一部分牌型种数则在cnt超过13时立即返回。剪枝的本质是提前判断这条路继续走有没有意义而不是等走到终点再后悔。建议每写完一个DFS都问自己一句每一个递归分支里有什么信息能提前排除掉一部分方案4.4 按值传递容器性能灾难的隐形来源用C做题时有人习惯把path直接作为参数按值传递因为这样代码写起来天然无副作用递归返回后不需要恢复现场。数据量小的时候确实没感觉一旦n到了15以上每次递归都拷贝整个vector复杂度直接爆炸运行时间从毫秒级变成秒级。修正方法就是前面强调过的传引用手动恢复。如果你实在担心引用导致状态污染那就先在纸上把标记、递归、撤销的流程画清楚而不是用拷贝来掩盖逻辑不清。Python选手没有引用的困扰但也要注意别在函数内部反复切片推荐用列表append/pop配合位置索引。4.5 递归栈溢出极端数据下的终极方案DFS天然依赖系统栈如果数据规模到几万层C默认栈往往不够用程序直接崩溃。蓝桥杯大多数题不会这么极端但万一遇到比如某些图的路径枚举有两个应对方案一是把递归改成显式栈用stackpairint,int模拟DFS二是使用全局大数组配合迭代写法。我的建议是如果题目明说图很大优先考虑BFS或显式栈别再头铁递归。5. 与BFS的边界判断什么情况别用DFS硬刚第四天复习到这儿必须把DFS和BFS的适用边界理清楚。搜索题碰到求最短步数最少操作次数时不少同学还是条件反射DFS结果跑出正确答案但超时这是最可惜的丢分方式。对比维度DFSBFS空间复杂度一般较低栈深度可能较高队列宽度是否能求最短路不行首次找到的路径不一定最短可以首次找到即最短适合场景方案枚举、连通块、路径存在性最短步数、最少操作、层序遍历代码风格递归回溯代码短队列循环框架固定判断标准我总结成一句话题目问有没有有多少种用DFS题目问最少几步最短路径用BFS。蓝桥杯真题里像走迷宫最短路径最少交换次数基本都是BFS的地盘强行DFS只会换来超时。还有一个容易纠结的情况DFS能求出所有路径后取min为什么还不能替代BFS因为DFS枚举所有路径的时间是指数级的图一大就跑不动BFS利用每一层距离1的特性天然避免重复探索更远的分支效率完全不在一个量级。所以别用战术上的勤奋掩盖战略上的偷懒看清题目问什么再选算法。当然也有例外如果图中每个点只能走一次且图很小比如不超过10个点DFS全路径枚举也能过但这不是通法只适合数据规模极小的特殊情况。6. 第四天收尾今晚的练题清单与考场提速技巧复习的最后阶段我会把下一个阶段要练的题按类型列成清单每一类配上时间预估免得明天醒来又像无头苍蝇。这不是标准答案但如果你也是冲刺期的选手可以直接照着抄。题目类型蓝桥杯类似考点建议用时练习目标全排列变体带分数凑算式30分钟/题熟练恢复现场去重剪枝连通块类岛屿数量全球变暖20分钟/题稳固方向数组和边界顺序组合计数类牌型种数生日蜡烛25分钟/题掌握可行性剪枝路径枚举类剪格子方格分割40分钟/题综合考察标记/回溯/剪枝模拟搜索龟兔赛跑预测变体35分钟/题状态参数设计能力练题之外我想分享三个考场提速技巧都是今晚总结出来的。第一先写框架再补剪枝。很多同学一上来就想着怎么剪枝结果递归逻辑还没跑通剪枝条件反而把正确性搞崩了。正确顺序是先写一个不剪枝但一定正确的版本在小数据上验证通过再逐条加剪枝每加一条就测试一次。这个习惯能让你在赛场上少改半小时。第二打表验证小数据。DFS题容易受到递归顺序影响写出结果后先别急着交用n3或4的小数据手工验证一遍或者用暴力法对拍。蓝桥杯虽然不能对拍但你可以在本地快速验证逻辑是否正确能拦住九成低级错误。第三刻意减少参数数量。函数参数越多越容易传错我写DFS时能放全局的绝不放参数。但记住需要恢复的共享状态放全局时一定要配套写清楚撤销逻辑别省这一步。第四天走到这里DFS的框架、模型、坑位、算法边界都过了一遍。我自己的体会是学DFS最大的门槛不是递归本身而是什么时候进、什么时候退、什么时候剪的判断经验这种经验只能靠大量代码喂出来。如果你也在备赛路上建议按框架→模型→坑位→选型这个顺序过一遍会比埋头刷题快很多。最后再分享一个小技巧我习惯把今天踩过的坑直接写成注释贴在模板代码顶部比如恢复现场必须对称书写越界判断永远在第一行之类的。等上了赛场这些注释会变成条件反射帮你省下大量宝贵的debug时间。