企业官网建设流程全解析

准备蓝桥杯省赛，如果把所有算法按出现频率排个序，DFS与回溯绝对能进前三。不少同学一听到这两个词就觉得玄乎，觉得又是递归又是状态还原的，绕来绕去把自己绕晕。其实拆开了看，就是个“往下走到底，不行就回头换个路口再走”的模型，真正难的不是理解，而是把它写成一坨不会出错、能快速套用的代码。这篇日记我就把DFS和回溯的模板彻底拆开，从三类写法到剪枝套路，再到几道省赛常客题型的完整推演，一次讲透。适合所有准备蓝桥杯省赛的选手，也适合刚学算法想建立搜索体系的朋友。

1. 为什么说DFS是省赛之魂：题型分布与拿分逻辑

蓝桥杯省赛的难度其实很有规律，它不像ACM那样考大量复杂的数据结构和高级图论，反而特别偏爱“思路直接、写法固定、考你细节”的题目。DFS就是这类型里的代表人物。

从近几年的真题分布来看，省赛题目里能用DFS或回溯直接解决的题，比例相当高。比如排列组合类、子集枚举类、迷宫路径类、棋盘放置类、连通块统计类，甚至部分“暴力枚举”的填空题和编程大题，本质上都是DFS的套壳。而这些题目有一个共性：只要模板写得熟练，就算不会高级优化，也能拿下一大半的分。

这里有个很重要的判断标准：一道题如果你想不到什么高级算法，但数据范围又不大（比如n小于20），那大概率就是DFS。因为DFS结合剪枝之后，实际运行次数往往远小于最坏情况的阶乘或指数级，而蓝桥杯省赛的数据量设计，很多时候就是故意留给DFS走的。

另外还要明白一点：DFS不只是“搜索答案”的工具。它还能用来生成排列、枚举子集、检测连通性、走迷宫找路径、处理回溯型的状态推导。我们常说的“爆搜”，指的是用DFS把答案空间完整走一遍，配合剪枝把无效分支提前砍掉。理解了这套逻辑，你在考场上就会形成一种直觉：先看数据范围，能DFS就DFS，不要纠结有没有更“高级”的做法。

为什么很多同学写得慢、写得乱？多半是因为对“递归函数到底在干嘛”缺少画面感。DFS本质上是递归函数在状态空间里做深度遍历，你只需要关心三件事：当前到了哪一步、还有哪些选择、什么时候该停。把这三件事想清楚，代码自然就写出来了。

2. DFS与回溯的三类核心写法模板

2.1 递归版基础格式：最简单也最常用

先看一个最朴素的DFS模板。这个模板适用于“在集合里选/不选”、“走迷宫”、“枚举状态”等大量问题。

def dfs(当前状态, 路径记录): # 1. 终止条件 if 达到目标条件: 记录结果 / 输出结果 return # 2. 遍历当前层所有的“选择” for 每个可选择项 in 候选集合: if 不满足约束条件: continue # 剪枝或跳过 做选择（标记/加入路径） dfs(下一步状态, 路径记录) # 递归进入下一层 撤销选择（取消标记/弹出路径）

这个模板里最关键的就是最后两步：做选择和撤销选择。这一组操作合起来就是传说中的“回溯”。理解它可以这么想：递归进去是往下一层走，撤销是为了能回到本层，尝试下一条路。没有了撤销，你会在错误的路径上越走越远，最终得到的答案全是错的。

举一个最经典的场景——全排列。假设要从1到n生成所有排列，你直接套模板就能写：

def dfs(depth): if depth == n: result.append(path[:]) # 记录当前排列 return for i in range(1, n + 1): if used[i]: continue used[i] = True path.append(i) dfs(depth + 1) path.pop() used[i] = False

这里used数组负责标记某个数是否已经被用过了。没做标记就会重复使用，做了标记但忘了撤销，那下一层递归回来后就再也没法选这个数了，结果就是排列数量直接缩水。

2.2 全局变量版回溯：适合处理“记忆搜索和状态压缩”

递归版模板是最容易写的，但有些场景下，比如需要“记住”整个棋盘状态、需要做状态压缩、需要频繁修改全局数据结构的场景，用局部参数传递会非常吃力。这时候全局变量+回溯就更好用。

以八皇后为例子，用三个数组记录哪些列、哪些主对角线、哪些副对角线已经被占用：

col = [False] * n diag1 = [False] * (2 * n - 1) # r + c diag2 = [False] * (2 * n - 1) # r - c + n - 1 res = [] def dfs(r): if r == n: res.append(方案) return for c in range(n): if col[c] or diag1[r + c] or diag2[r - c + n - 1]: continue col[c] = diag1[r + c] = diag2[r - c + n - 1] = True board[r][c] = 'Q' dfs(r + 1) board[r][c] = '.' col[c] = diag1[r + c] = diag2[r - c + n - 1] = False

这个写法的优势在于：状态保存在数组里，递归函数只需要关心行号，传参少、访问快。省赛大部分题目用这种方式写就够用了。配合主对角线、副对角线的下标映射，很多看起来复杂的棋盘题都能套用。

这种全局变量回溯法还有个额外好处：方便“判重”。当你要走迷宫时，visited数组是全局的，回溯时还原visited，下一层搜索就能看到完整的环境视野，而不必像传参那样把整个地图拷贝一份。

2.3 带状态参数版：不用还原现场的另类写法

有不少教材会介绍一种“不用还原现场”的DFS写法：每一层递归把状态复制一份传给下一层，这样上层状态永远不会被修改。

def dfs(depth, selected, path): if depth == n: result.append(path[:]) return for i in range(1, n + 1): if selected >> i & 1: continue dfs(depth + 1, selected | (1 << i), path + [i])

这种写法用了位运算来记录哪些元素被选中了，selected本质是一个二进制掩码，某一位置1表示该数已被用过。由于每次进入递归都生成新的selected，当前层的掩码不会被改动，所以不需要回溯还原。

这个版本的最大优点就是代码极其简洁，而且不容易出错——你根本不会忘记撤销。缺点也明显：每次递归都要复制数据，内存和时间开销更大，当n达到十五六的时候性能可能会明显下降。蓝桥杯省赛里，n一般在10到20之间，如果你对位运算和函数式编写不熟，还是推荐用全局变量版，更稳更直观。

我个人建议：考场优先写全局变量回溯版。因为它思路统一，不需要考虑拷贝开销，出bug概率也更低。带状态参数版大多出现在需要特殊优化的题里，比如状压DP配合DFS记忆化搜索时，用掩码传递就比还原全局数组快得多。

3. 剪枝，才是真正拉开差距的地方

模板本身不值钱，值钱的是你怎么剪枝。蓝桥杯省赛的DFS题，很多时候裸搜索是能过的，但也有不少题裸搜会超时，会不会剪枝直接决定你是拿满分还是拿部分分。

3.1 可行性剪枝

最简单也最常用的剪枝，就是判断当前状态下，就算把剩下的所有机会都用上，还有没有可能到达目标。如果没有可能，直接return。

举一个典型例子：给定一些数字，要求凑成某个目标值。搜索时如果当前累计和已经大于目标值，后面怎么加都超了，那就没必要再递归。

def dfs(idx, current_sum): if current_sum == target: ans += 1 return if current_sum > target: return if idx == n: return # 不选当前元素 dfs(idx + 1, current_sum) # 选当前元素 dfs(idx + 1, current_sum + nums[idx])

这看起来简单，但很多新手会漏掉current_sum > target这一行。加了这一行，指数级的搜索树瞬间砍掉一大半。这里的逻辑就是：搜索过程中持续“看未来的路是不是已经堵死”，堵死了就撤。

3.2 最优性剪枝

最优性剪枝针对的是“求最小步数、最大价值、最少代价”这类问题。当你已经找到当前最优解时，如果某条分支的前缀代价已经不会更优，就直接放弃。

举例：走迷宫求最小步数，你已经找到了一个步数为10的路径。当DFS搜到某一点时，走过的步数已经等于10，后面就算直接到终点也是10步，不可能更少，所以剪掉。更精细一点，可以用当前步数 + 曼哈顿距离和最优答案比较，提前剪掉明显没希望的分支。

def dfs(x, y, step): if step >= best: return if x == ex and y == ey: best = step return # 继续向四个方向搜索

这里best存的是全局最优解。每一步都检查一下，一旦发现当前步数不可能刷新记录，直接取消递归调用。这个剪枝配合BFS确实可以大幅减少搜索量。

3.3 排除等效冗余

有些搜索顺序是重复的。比如组合问题C(n, k)，从集合中选k个元素。如果你按排列的方式去搜，得到的很多结果其实是同一个组合的重复排列。这时候只要在DFS里强制“下标递增”，就能避免重复搜索。

def dfs(start, depth, path): if depth == k: result.append(path[:]) return for i in range(start, n): path.append(nums[i]) dfs(i + 1, depth + 1, path) path.pop()

关键在dfs(i + 1, ...)，保证下一个元素始终是当前元素后面的，这样就生成了唯一有序的组合序列。这种“下标递增”是组合枚举的标准写法，写熟了能少算很多重复分支。排列问题和组合问题的一个重要区别就在这里：排列需要用visited标记来避免重复选择，组合只用start下标就够了。

3.4 奇偶性剪枝与针对性陷阱

迷宫题里有一种很经典的特殊剪枝，叫奇偶剪枝。核心含义是：从起点到终点的最短路径的步数奇偶性，和曼哈顿距离的奇偶性是一致的。如果剩余步数和曼哈顿距离的奇偶性不一样，那无论怎么绕，都不可能恰好走完。

这个判断写起来非常简单：

if (remaining_steps - manhattan_distance) % 2 != 0: return # 必死无疑

我第一次在蓝桥杯训练题里用这个剪枝时，心里还挺没底，结果实测直接让一个原本会超时的迷宫题变成秒出。它的原理其实也不玄：每走一步都会改变当前坐标的“曼哈顿校验值”的奇偶，绕路只会增加偶数步，所以总步数的奇偶必须等于最短路径的奇偶。

还有一类“针对性剪枝”视题目而定，比如数独搜索时先枚举可选数最少的位置，这就是所谓的“启发式排序”或“优先选择约束最多的分支”。放到迷宫搜索里就是优先走那些下一步分支更少的方向。这种优化不改变代码复杂度，但对运行时间的影响非常可观。

4. 实战复盘：三道经典省赛题型手把手拆解

4.1 全排列与下一项枚举：从暴力到字典序

全排列作为DFS入门题，代表了一批“枚举所有排列”的题目。它看起来很简单，但蓝桥杯经常给它穿个马甲，比如“数字游戏”“组队方案”“算式填空”，核心还是排列枚举。

我建议把它至少写三遍：第一遍复习模板，第二遍练剪枝去重（如果有重复元素），第三遍用字典序法推演如何按题目要求的顺序输出。

重复元素的全排列去重是一个高频考点。如果数组里有重复数字，你直接套模板会输出大量重复排列。解决办法是在同一层循环里，如果某个数字被用过，或者它和前一个数字相同且前一个数字没被用，就跳过。

for i in range(n): if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue used[i] = True path.append(nums[i]) dfs(...) path.pop() used[i] = False

这个去重条件很多人抄下来了，但不理解为什么。其实逻辑是：保证相同数字在同一层DFS里只被选择一次。如果前一个相同数字没被用，说明当前这个数字就是重复开口，跳掉它，就能避免从两条完全相同的分支分别搜出相同结果。

4.2 八皇后与棋盘类问题：状态映射是核心

省赛的棋盘问题出得非常多，比如N皇后、马走日、车的攻击范围、黑白棋盘翻转等。这些题统一的特点是需要你把棋盘坐标映射到各种约束状态里。

八皇后我上节列过代码，这里再说两个操作细节。

第一，行号和列号从0开始计，那么左上到右下的对角线编号是r - c + n - 1，加上偏移量保证了数组下标非负；右上到左下的对角线编号是r + c。这个映射关系要是记错了，整个棋盘就乱了。

第二，当n较大的时候，对称性剪枝可以让搜索量几乎减半。第一行皇后只需要枚举半个棋盘，因为整幅棋盘左右对称，右边的情况是左边的镜像。这个剪枝在n=13、14的时候表现得非常明显，省赛里n一般不大，但如果命题人故意把n给到十几，普通DFS没过，加了对称剪枝可能就稳了。

棋盘类的通用模板基本都长这样：

def dfs(row): if row == n: ans += 1 return for col in range(n): if 列冲突 or 主对角线冲突 or 副对角线冲突: continue 标记三个冲突数组 dfs(row + 1) 还原三个冲突数组

只要你会八皇后，大部分棋盘题都能从这套模板拓展过去。唯一的区别就是冲突状态的维护方式，有的用数组，有的用位运算，有的用set。

4.3 迷宫寻路与连通块：搜索的同时记录路径

迷宫题在省赛里分成两类：一类是问“能不能从起点到终点”，另一类是问“最短路径有几条”。前一类用DFS也完全OK，后一类更推荐BFS，但如果你已经熟写DFS，用DFS加剪枝也能做，就是复杂一些。

对于“能不能到”，DFS写法极其简单：

def dfs(x, y): if x == ex and y == ey: return True visited[x][y] = True for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny = x + dx, y + dy if 边界ok and map[nx][ny] == '.' and not visited[nx][ny]: if dfs(nx, ny): return True return False

这里有个容易踩的坑：一旦找到终点就层层返回True，返回值设计得像“短路开关”。你要是不设返回值，而是靠全局变量标记是否找到，常常因为递归层数太多而提前return，导致漏掉结果。

连通块统计是迷宫题的变种。比如计算陆地面积、统计岛屿数量，套路都是遍历每个未访问的格子，每次遇到新连通块就做一次DFS，把整个块标记完。

def solve(): ans = 0 for i in range(n): for j in range(m): if grid[i][j] == '#' and not visited[i][j]: ans += 1 dfs(i, j)

这道题的坑在于很多人会在DFS里改全局块的计数，结果每个格子都加一遍，答案直接翻好几倍。正确做法是：每次进入一个新的未访问格子，计数器加一次，然后递归去把邻居全部纳入这个块。

5. 常见问题与排查技巧实录

5.1 递归超时？先别急着换算法

遇到DFS超时，第一反应不要是“怎么改成动态规划”，而是检查你的搜索是不是有大量无效分支。八成问题出在缺少剪枝。先把所有可能的可行性剪枝加上，再用最优性剪枝，最后考虑加启发式排序。绝大多数蓝桥杯题做到这一步就通了。

我之前写过一道子集问题，数据量n=25，裸DFS怎么跑都超时。后来加了一个预排序+前缀和剪枝：先把数组从大到小排序，同时预处理后缀和，搜索时如果当前累加值加上后缀和都无法到达目标，直接剪掉。结果运行时间从几十秒降到了零点几秒。

5.2 输出顺序不对，可能是你的遍历顺序有问题

DFS全排列默认是字典序输出，只要你的候选列表是有序的，且循环按顺序遍历。但如果题目对输出顺序有特殊要求，比如“按字典序的逆序”或“按某种自定义优先级”，你只需要调整for循环里候选集合的排列顺序就行。

还有种情况是结果路径本身有序但输出时顺序乱了。检查你是不是直接把result倒序打印了，或者递归返回后忘了path已经是空而打印的是全局变量。打印时用path[:]复制，不然循环里的path会一直变。

5.3 忘记还原现场，答案诡异翻倍或缺漏

“还原现场”是回溯最经典也最容易翻车的地方。典型症状：输出的排列数少于预期，或者结果中混入了重复数据。排查方式很简单：在每次continue和递归调用返回之后，检查所有标记数组是否回到了进递归前的状态。

我的习惯是：把“做选择”和“撤销选择”两行代码写在紧挨递归调用的上下两行，中间不插任何代码。看到if分支里提前return但没还原，多半就是这个bug的来源。在“迷宫连通块”统计这类不需要还原的DFS里，忘记加visited却会导致栈溢出或死循环，需要区分对待。

5.4 栈溢出怎么办

DFS用递归，蓝桥杯一般递归深度也就几百到几千层，不会爆栈。但如果你写的是长链递归，比如单链表路径1万层，Python默认递归深度上限1000就可能报错。这时候用sys.setrecursionlimit临时调高是常见做法。

import sys sys.setrecursionlimit(1 << 25)

不过我不推荐无脑调高。深度太大时，更好的做法是用栈模拟DFS，把递归改成显式栈。省赛还真出过一道题，数据范围故意做成会导致深递归的形态，用递归写就爆栈，用栈模拟就稳稳过。这也算一个“反直觉”的考点。

5.5 各种小坑速查表

6. 从模板到变体：DFS还能这么玩

DFS和回溯不止是暴力枚举，它还是很多高级算法的基底。这里列几个省赛可能涉及的变体方向，帮你拓宽思路。

第一个是“DFS + 状态压缩”。当搜索状态是若干个0/1开关时，可以用整数位掩码来表示。比如“开关灯”类问题，一行的状态用一个整数存储，DFS转移时用异或改变状态。这种写法不仅快，还方便用字典做记忆化搜索。记忆化的本质是：如果某个状态已经访问过且结果已知，就直接返回，不再重复搜索。DFS加上记忆化，就有了一批“伪DP”的效果。

第二个是“DFS生成括号序列”。合法的括号序列生成、括号配对检测，都是DFS的一个变种。状态设计非常直观：左括号用了几个、右括号用了几个，约束条件就是任何前缀里右括号数不超过左括号数。

def dfs(l, r, path): if l == n and r == n: result.append(path) return if l < n: dfs(l + 1, r, path + '(') if r < l: dfs(l, r + 1, path + ')')

这道题的价值在于，它展示了“约束条件跟着状态走”的写法。很多时候DFS不光是穷举，更是在一堆状态转移里筛选合法路径。

第三个是“图论中的连通性DFS”。判断两个点之间是否有路径、求无向图连通分量个数、判断是否有环，全是同一套DFS思路。只不过这时你不需要回溯还原，因为图搜索走过了就是走过了，不需要回去换路。

这类题的模板和迷宫题完全一致，应用场景却能延伸到很多更复杂的模拟题里。省赛里出现过“数独立块儿”“找最大岛屿面积”等题，本质上就是在图上做DFS并把整块标记染掉。

第四个是“迭代加深DFS（IDDFS）”。当答案可能在很浅的层，但直接深搜会无限钻下去时，可以用迭代加深：先限制深度为1搜一遍，再到2，再到3……这种方式兼具BFS的“浅层优先”和DFS的“内存省”两大优点。省赛偶尔在“最少步数”类题里考到，如果你BFS状态空间太大而DFS又不知道深度上限，迭代加深就是个极好的折中方案。

7. 考场上的编码节奏与心态管理

最后聊一点非技术部分，但我觉得这同样重要。蓝桥杯省赛一道DFS题代码量通常不超过50行，真正耗费时间的不是写代码，而是把状态设计、终止条件、剪枝判断想清楚。

我的个人顺序是：先在草稿纸上画一个小规模的搜索树，把每一层是什么、每层的候选集合是什么标出来，然后再对照模板写。这一步很多人觉得多余，但实测下来，能省掉至少一遍调试时间。你只要把“节点状态”和“转移方式”想明白，代码几乎就是照着模板填的。

想到一个题可以用DFS时，还要顺势判断一下题目的数据范围能不能跑完。比如n=20的所有子集枚举是100万级别，完全没问题；但n=30的就是10亿级别，裸搜会炸。判断标准不用太精确：指数级增长的搜索，底数每大一点，运行时间就会差出好几个数量级。感觉不对就要果断考虑剪枝、换算法或换搜索顺序。

考场上时间分配也建议有一个固定策略：先把所有题过一遍，找出DFS和回溯的题，优先把稳的分拿到手。因为这些题你只要会模板就等于会了，不像有些动态规划题还需要现场推导转移方程。拿分效率高，性价比也高。先把它们解决，心里就踏实了一半。

我自己的习惯是把DFS模板在草稿纸上背写两遍，进考场先默写这么几行，算是热身。等到真正遇到题目时，手已经在状态了，写起来自然流畅许多。准备蓝桥杯省赛，DFS就是那个值得你花一整个下午去彻底吃透的知识点，后面的算法树再往上长，很多枝丫都是从这里分出去的。