企业官网建设流程全解析

把“蓝桥杯”“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全排列可以过掉一部分不算大的n；DFS配合简单剪枝后，常常能从超时边缘拉回到可接受范围。换句话说，DFS是一个“保底手段”，也是很多难题的兜底策略。

1.2 为什么第五天需要专门“盘”一遍DFS

前面四天如果只在搞基础语法和简单枚举，那你可能还没真正理解“递归函数栈”的展开过程；如果已经刷了一点DFS，但每次写完总差那么几个剪枝，那更需要系统梳理。第五天做DFS专项，目的不是刷题量，而是建立稳定的“深搜思维模板”。

我见过不少同学，DFS代码能默写，但一到考场就出问题：要么不知道什么时候该回溯，要么访问状态没还原，要么数据一大直接栈溢出。归根结底是脑子里没有一套“什么时候进入下一层、什么时候恢复现场、什么时候剪枝”的判断框架。这一天的核心任务，就是把这套框架固化下来。

还有一个现实原因：蓝桥杯省赛时间紧，四道编程大题连做带调，中间没有太多时间给你“现场推倒重想”。如果DFS模板能直接秒套，省下来的时间可以留给后面的DP题目。所以今天的内容不是教你新鲜概念，而是把高频模式压缩成可以直接调用的“肌肉记忆”。

2. DFS的底层框架：递归树、参数设计与回溯三件套

2.1 深搜到底在搜什么

DFS的全称是Depth First Search，深搜。它做的事情本质上是“沿着一条路走到黑，走不通就回头换下一条”。这句话听起来简单，但代码里要落地，核心是靠“递归函数里的参数”和“当前状态的修改/恢复”配合完成。

想象你在走迷宫：每到一个岔路口，先选择第一个方向走到尽头；如果尽头是死路，就退回岔路口，再挑下一个方向。计算机里的“退回来”，就是函数返回后，把之前改过的状态变量还原到进入递归前的样子。这也是为什么DFS老手都会反复强调“回溯时恢复现场”。如果你写的是二叉树遍历那种不需要恢复的递归，那叫“先序遍历”；一旦涉及棋盘、排列、路径、连通块，基本都要和“状态标记”打交道。

举个例子，全排列问题求{1,2,3}的所有排列：

vector<int> 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 递归出口怎么写才不容易错

递归出口是深搜里最“凭感觉”的部分，但蓝桥杯的题基本就两类：一是“枚举完所有位置”出口，比如全排列的depth==n、棋盘填完最后一行；二是“找到目标状态”出口，比如迷宫出口坐标匹配、通过某种条件判断成功。出口写太早，会漏解；写太晚，会多搜很多无效层。

我的习惯是先把出口写在函数最前面，再处理剪枝。先判断“当前状态能不能直接得到答案”，再判断“还有没有继续搜的必要”。比如数独填充题，出口通常是“所有空格填完”，因为这时候才真正生成了一个完整棋盘。如果你在填到一半就输出，必然出错。

出口处还有一个容易丢分的点：多组解的去重。有些题目要求“字典序最小”或“升序排列”，你在出口拿到一组结果后需要判断顺序。实操中很多人会先在递归里生成全部排列，最后用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，差距是天上地下。

按我的经验，蓝桥杯常用的剪枝有三种：

1. 可行性剪枝：当前状态明显不合法，直接return。比如N皇后里当前列已经有皇后，不需要往下搜；数独里填入的数字与行、列、宫冲突，直接跳过。
2. 最优性剪枝：当题目要求最短步数、最少花费时，如果当前步数已经超过已知最优解，后面再怎么走都不可能更好，直接return。
3. 冗余性剪枝：对结果无影响的对称、平移、首元素固定等，提前排除重复分支。全排列固定第一个数就是典型的冗余性剪枝。

有一个容易被忽略的坑：剪枝条件写错，会把正确解也剪掉。建议每加一个剪枝，先用小样例验证，再跑一次暴力对比。不要一上来就“大胆剪枝”，剪出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 全排列枚举+条件判断：暴力拿分的快乐

很多蓝桥杯编程大题，尤其是数据范围在n<=10的题，本质就是全排列穷举。比如“数字拼接成最大整数”“排列后判断是否能整除”“n个数的运算符插入”。这类题不需要高端优化，只要写出标准全排列框架，在出口处判断条件即可。

我的建议是：如果题目里n不大，先别急着想数学规律，直接DFS全排列暴力。蓝桥杯的判题数据里，n小这种情况非常常见。很多“原创题”其实就是把DFS包装得花里胡哨，背后的搜索树节点数并不多。暴力能拿70%的分，剩下的再想优化也来得及。

验证全排列DFS是否正确，有个实用技巧：找一个n=3或n=4的小数据，手算预期结果，然后让程序输出所有排列，看看数量和字典序是否符合预期。这一步能排查掉大部分“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，先估一下数据范围。n<=10，直接全排列；n<=20，可以考虑状态压缩或DFS+剪枝；n<=100，多半需要对搜索做记忆化或改用DP。不要在单个题上死磕，如果DFS写了20分钟还没跑通，先跳到下一题，回头再用暴力拿基础分。

另一个考场技巧是：先写一个不优化的DFS，保证能出正确答案，再逐步加剪枝。很多同学一上来就开始“高性能剪枝”，结果剪枝有bug，连基础分都丢了。先暴力、后剪枝、最后一小时统一优化，是稳妥策略。即使在国赛，这种“由正确到高效”的顺序也远比“上来就追求最优”靠谱。

7. 第五天冲刺实操清单与个人经验总结

如果今天只有一天时间，我会建议你按下面这个顺序练：

1. 手写一遍全排列、组合、子集的DFS模板，并各运行一次，确认输出数量正确。
2. 刷2~3道连通块题，把方向数组、vis标记、面积统计练熟。
3. 刷2~3道回溯题，重点是N皇后或数独，掌握“状态恢复”和“对角线标记”。
4. 刷2~3道剪枝题，体验从超时到AC的完整过程。
5. 留一小时做一套真题里的DFS部分，模拟考场时间。

题单不用贪多，一天能高质量完成十道题已经不错。重点不是“量”，而是每道题都能回答三个问题：搜索状态是什么？出口怎么判断？剪枝依据是什么？

就我个人经历来说，DFS是蓝桥杯冲刺阶段“性价比”最高的板块之一。它的入门门槛低，但天花板很高——从暴力穷举一路延伸到记忆化搜索、迭代加深、启发式剪枝，整个知识链几乎覆盖了搜索题的全部考点。第五天专门花一整天来盘它，后面学DP、图论时会觉得思路顺畅很多。尤其到考前模拟阶段，看到新题时能条件反射地画出递归树，这种“肌肉记忆”就是这天的收获。