企业官网建设流程全解析

今天是冲刺蓝桥杯打卡的第四天。前三天我把递归基础、回溯框架和常见模板题过了一遍，今晚准备把DFS板块整体收尾。说句实话，DFS这块内容真学透了，蓝桥杯省赛至少能拿到两成以上的分——不管是填空里的排列组合题，还是编程大题里的地图遍历、路径计数、模拟枚举，DFS都是最常见的切入方式。这篇文章就当作我今晚的复习笔记，从底层递归逻辑到真题模型，再到踩坑记录，完整梳理一遍，也给我后面十几天的刷题留个索引。

先说清楚读者定位：如果你已经会写基本的递归函数，但对DFS的"边界条件、恢复现场、剪枝时机"还比较模糊；或者你刷了不少题但总在某个环节超时、重复、漏解，那这篇文章应该能帮上忙。如果你完全是零基础，建议先找一套全排列模板题跑通，再回来看，效果会好很多。

1. 为什么第四天还在死磕DFS：蓝桥杯里的考察密度与复习策略

先看蓝桥杯省赛的题目结构：一共10道题，5道填空、5道编程，覆盖枚举、模拟、贪心、动态规划、搜索、数论等方向。其中DFS/BFS是搜索类问题的绝对主力，几乎每年都有至少一道编程大题直接考搜索，填空题里也经常出现"能排列多少种方案""有多少种走法"这类需要用DFS枚举的题目。我统计了近五年的真题分布，大致是这样的场景：

当然这个表只是我个人刷题后的归纳，不是官方统计，但趋势很明显：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(vector<int> path) { ... } // 正确示范：传引用，用完撤销 void dfs(vector<int>& 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就不需要撤销，递归函数里加一层cnt+k再传下去，本来就是不可变的。

// 组合类：不需要恢复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~13），cnt表示已选牌数 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=-1，vis[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++默认栈往往不够用，程序直接崩溃。蓝桥杯大多数题不会这么极端，但万一遇到（比如某些图的路径枚举），有两个应对方案：一是把递归改成显式栈，用stack<pair<int,int>>模拟DFS；二是使用全局大数组，配合迭代写法。我的建议是：如果题目明说图很大，优先考虑BFS或显式栈，别再头铁递归。

5. 与BFS的边界判断：什么情况别用DFS硬刚

第四天复习到这儿，必须把DFS和BFS的适用边界理清楚。搜索题碰到"求最短步数""最少操作次数"时，不少同学还是条件反射DFS，结果跑出正确答案但超时，这是最可惜的丢分方式。

判断标准我总结成一句话：题目问"有没有""有多少种"用DFS；题目问"最少几步""最短路径"用BFS。蓝桥杯真题里，像"走迷宫最短路径""最少交换次数"基本都是BFS的地盘，强行DFS只会换来超时。

还有一个容易纠结的情况：DFS能求出所有路径后取min，为什么还不能替代BFS？因为DFS枚举所有路径的时间是指数级的，图一大就跑不动；BFS利用"每一层距离+1"的特性，天然避免重复探索更远的分支，效率完全不在一个量级。所以别用战术上的勤奋掩盖战略上的偷懒，看清题目问什么再选算法。

当然也有例外：如果图中每个点只能走一次，且图很小（比如不超过10个点），DFS全路径枚举也能过，但这不是通法，只适合数据规模极小的特殊情况。

6. 第四天收尾：今晚的练题清单与考场提速技巧

复习的最后阶段，我会把下一个阶段要练的题按类型列成清单，每一类配上时间预估，免得明天醒来又像无头苍蝇。这不是标准答案，但如果你也是冲刺期的选手，可以直接照着抄。

练题之外，我想分享三个考场提速技巧，都是今晚总结出来的。

第一，先写框架，再补剪枝。很多同学一上来就想着怎么剪枝，结果递归逻辑还没跑通，剪枝条件反而把正确性搞崩了。正确顺序是：先写一个不剪枝但一定正确的版本，在小数据上验证通过，再逐条加剪枝，每加一条就测试一次。这个习惯能让你在赛场上少改半小时。

第二，打表验证小数据。DFS题容易受到递归顺序影响，写出结果后先别急着交，用n=3或4的小数据手工验证一遍，或者用暴力法对拍。蓝桥杯虽然不能对拍，但你可以在本地快速验证逻辑是否正确，能拦住九成低级错误。

第三，刻意减少参数数量。函数参数越多越容易传错，我写DFS时，能放全局的绝不放参数。但记住：需要恢复的共享状态放全局时，一定要配套写清楚撤销逻辑，别省这一步。

第四天走到这里，DFS的框架、模型、坑位、算法边界都过了一遍。我自己的体会是，学DFS最大的门槛不是递归本身，而是"什么时候进、什么时候退、什么时候剪"的判断经验，这种经验只能靠大量代码喂出来。如果你也在备赛路上，建议按"框架→模型→坑位→选型"这个顺序过一遍，会比埋头刷题快很多。

最后再分享一个小技巧：我习惯把今天踩过的坑直接写成注释，贴在模板代码顶部，比如"恢复现场必须对称书写""越界判断永远在第一行"之类的。等上了赛场，这些注释会变成条件反射，帮你省下大量宝贵的debug时间。