第四章 深度优先搜索DFS
第一单元：深度优先搜索 DFS 入门——走进迷宫，探索每一条岔路！
同学们，准备好了吗？
今天，我们要走进一座神秘的魔法迷宫。迷宫里有岔路、有宝箱、有机关，还有一扇通往终点的大门。
我们的任务是：
让计算机像一名勇敢的小探险家一样，沿着一条路不断向前探索；走不通了，就退回来，换一条路继续探索。
这就是今天要学习的算法——深度优先搜索，英文简称 DFS（Depth-First Search）。
它是信息学竞赛中非常重要的一种搜索算法。学会 DFS 后，我们就能解决迷宫寻路、排列组合、选取方案、图的遍历、八皇后等许多问题。
本单元将按照下面的路线展开：
第一站：认识 DFS
什么是深度优先搜索？它为什么要先走到底？
第二站：图示推演
一步一步走迷宫，学会前进、回退和搜索顺序。
第三站：基础代码与万能模板
从递归函数到 visited 数组，搭建自己的 DFS 工具箱。
第四站：典型例题与变式训练
从数数、走迷宫，到统计路径和枚举所有方案。
第五站：复杂度分析与自测
学会估算搜索规模，发现 DFS 最容易出现的错误。
第一站：什么是深度优先搜索？
1. 魔法迷宫里的探险家
很久以前，魔法王国里有一座迷宫。探险家从入口出发，要寻找藏在迷宫深处的宝箱。
他来到第一个岔路口，发现前面有两条路。
左边通道通向一个新的岔路口。
右边通道也通向一个新的岔路口。
应该先走哪边呢？
假设我们规定：有多条路可以走时，先走左边；沿着左边继续走，直到走不动了，再回来探索还没走过的路。
于是，探险家会这样行动：
选择一条尚未探索的道路。
沿着这条道路继续深入。
如果遇到新的岔路，继续向深处探索。
如果所有可走的道路都已经探索过，就退回上一个岔路口。
再探索其他尚未走过的道路。
这就是 DFS 的核心思想。
2. 为什么叫“深度优先”？
我们先比较两种探索方式。
深度优先搜索 DFS
先沿着一条路尽可能深入，走不通再回退。
关键词：一条路走到底，再回来。
广度优先搜索 BFS
先探索离起点近的一层，再探索下一层。
关键词：一层一层向外扩展。
今天我们专注学习 DFS。等以后学习 BFS 时，就会发现：两种搜索像两位性格不同的探险家，一位喜欢深入，一位喜欢先探索附近。
3. DFS 的三个关键动作
请记住这三个动作：
这三个动作看起来简单，却是很多 DFS 程序的共同基础。
第二站：图示推演——亲眼看见 DFS 如何搜索
例题一：探索一棵魔法树
迷宫可以画成道路图。为了先理解 DFS，我们把它简化成一棵树。
假设树上的房间连接关系如下：
这棵树的关系是：
A 连接 B、C；
B 连接 D、E；
C 连接 F、G。
从 A 开始，DFS 会如何访问？
第一步：从 A 出发
A 有两个孩子：B 和 C。
先走左边的 B。
访问顺序目前是：
A → B
第二步：继续深入 B
B 还有两个孩子：D 和 E。
先走 D。D 没有孩子了，于是回退到 B。
访问顺序：
A → B → D
注意：回退不是把 D 从访问记录中删除，而是让探险家返回上一个岔路口。
第三步：探索 B 的另一条路
回到 B 后，发现 E 还没有探索，于是进入 E。
E 没有孩子，继续回退。
访问顺序：
A → B → D → E
第四步：回到 A，探索 C
B 的所有分支都已经探索完毕，回到 A，进入 C。
再依次探索 F、G。
最终访问顺序为：
A → B → D → E → C → F → G
这是在“先左后右”规则下的 DFS 访问顺序。
如果我们规定先右后左，访问顺序就会改变。因此，DFS 的具体访问顺序与邻居的检查顺序有关，但它“深入后回退”的核心思想不变。
第三站：让计算机学会 DFS——递归是怎样工作的？
现在有一个关键问题：
探险家走不通时，为什么知道该回到哪个岔路口？
在程序里，我们可以用递归来实现这种探索过程。
1. 先理解递归
递归就是：一个函数在执行过程中，再次调用它自己。
例如：
void dfs(int x) { // 处理当前房间 // 继续探索下一个房间 dfs(下一个房间); }这段代码只是示意，不能直接运行，因为“下一个房间”还没有具体定义。
我们先把递归想象成一支探险队：
进入一个房间，就开启一层新的探索任务；
新任务探索完毕，返回上一层；
上一层接着寻找其他还没探索的道路。
2. 递归调用像一摞盘子
比如：
dfs(A);程序进入 A 后，调用：
dfs(B);程序进入 B 后，又调用：
dfs(D);当 D 没有可探索的房间时，dfs(D)执行结束，程序返回dfs(B)里尚未执行完的地方。
这就像把盘子一层层放上去，再一层层拿下来。
递归的调用过程不断深入，函数返回的过程就是回退。
3. 递归必须有停止条件
如果一个函数永远调用自己，会发生什么？
void dfs(int x) { dfs(x); }这个函数没有停止条件，会不断调用自己，最终可能导致程序崩溃。
所以，每个递归搜索都必须有合理的结束条件。例如：
if (x == target) { return; }这表示：如果已经到达目标，就结束当前这次探索。
不过，在真实的迷宫问题中，还需要处理边界、墙壁、访问记录等条件。接下来，我们逐步补齐这些内容。
第四站：DFS 基础代码与模板——建立自己的搜索工具箱
前面我们通过故事和图示认识了 DFS，现在正式进入代码世界。
初学时，不要急着背很多不同的 DFS 程序。先掌握一个基本结构，再根据题目逐步添加判断条件。
1. 最简单的递归模板
假设我们要从房间x出发，探索它的所有相邻房间。
void dfs(int x) { // 1. 处理当前房间 // 2. 枚举所有相邻房间 // 3. 判断能不能前往 // 4. 满足条件就继续 dfs(下一个房间) }这四步是许多 DFS 程序的共同骨架。
不过，真实搜索中经常会出现循环道路。比如 A 连着 B，B 又连回 A。如果不记录哪些房间已经访问过，程序可能永远在 A 和 B 之间来回探索。
所以，我们需要认识一个重要工具：visited数组。
2.visited数组：给探索过的房间盖章
我们可以用一个数组记录房间是否访问过。
bool visited[1005];它就像探险家的印章本：
visited[x] == false：房间 x 还没有探索过。
visited[x] == true：房间 x 已经探索过。
每次进入一个新房间，先盖章，再探索它的邻居。
void dfs(int x) { visited[x] = true; // 处理当前房间 x // 对每个与 x 相邻的房间 y： // 如果 y 没有访问过，就继续 dfs(y) }为什么要先盖章，再往下探索？
因为如果进入 B 后还没有给 B 盖章，就继续进入 A；A 又可能进入 B。这样，程序就可能不停重复。
记忆口诀：先标记，再深入；没访问，才进入。
3. 图的 DFS 通用模板
当题目给出一张图时，可以使用下面的模板。这里假设图的邻接表g[x]已经建好。
#include <iostream> #include <vector> using namespace std; const int N = 1005; vector<int> g[N]; bool visited[N]; void dfs(int x) { visited[x] = true; cout << x << " "; for (int i = 0; i < (int)g[x].size(); i++) { int y = g[x][i]; if (!visited[y]) { dfs(y); } } } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; // 无向图：两个方向都要记录 g[u].push_back(v); g[v].push_back(u); } int start; cin >> start; dfs(start); cout << endl; return 0; }例如输入：
5 4 1 2 1 3 2 4 3 5 1表示有 5 个顶点、4 条无向边，从顶点 1 开始搜索。
在邻接表按输入顺序存储邻居的情况下，输出：
1 2 4 3 5搜索过程是：
从 1 进入 2；
从 2 进入 4，4 没有未访问的邻居，返回 2；
返回 1，继续进入 3；
从 3 进入 5，之后结束。
这就是 DFS 在图上的完整探索过程。
4. DFS 模板的四个关键位置
代码位置 | 作用 |
|---|---|
| 标记当前顶点已经访问 |
| 处理当前顶点，本例是输出 |
| 依次检查相邻顶点 |
| 只进入尚未访问的顶点 |
要注意：邻接表模板适用于图的遍历。二维迷宫虽然也可以用 DFS，但需要另外检查上下左右四个方向，以及地图边界和墙壁。
第五站：典型例题一——迷宫探险，能不能找到出口？
这是 DFS 最经典的入门应用。
题目背景
小勇士进入了一座 6 * 6 的迷宫。
S表示起点；E表示终点；#表示墙壁；.表示可以通行的道路。
勇士每次只能向上、下、左、右移动一格，不能穿过墙壁。
请判断：能否从起点到达终点？
1. 先把迷宫变成二维数组
我们用字符数组保存地图：
char maze[105][105];例如：
S...# ##..# ...## .#..E .....每个字符就是一个格子。
如果当前位置是(x, y)，那么四个方向可以表示为：
方向 | 新行号 | 新列号 |
|---|---|---|
上 |
|
|
下 |
|
|
左 |
|
|
右 |
|
|
我们把方向变化放进两个数组中：
int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};当i从 0 到 3 时：
nx = x + dx[i]; ny = y + dy[i];就可以依次得到上、下、左、右四个相邻格子。
这是一种很常用的网格搜索写法。
2. 迷宫 DFS 的思考步骤
每次进入一个格子，我们要做四件事：
如果已经到达终点，说明找到出口。
标记当前格子已经探索过。
枚举上、下、左、右四个方向。
只进入没有越界、不是墙壁、尚未访问过的格子。
为什么还需要访问标记？
因为道路可能连成环。例如走上两步、右两步后，又可能通过另一条路返回原来的位置。如果不记录访问状态，搜索可能反复绕圈。
3. 完整 C++参考程序
输入格式：
第一行输入
n m；接下来输入
n行迷宫；每行包含
m个字符；地图中有一个
S和一个E。
#include <iostream> using namespace std; const int N = 105; int n, m; char maze[N][N]; bool visited[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int sx, sy, ex, ey; bool found = false; void dfs(int x, int y) { if (x == ex && y == ey) { found = true; return; } visited[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 (maze[nx][ny] == '#') { continue; } // 已经访问过，不重复进入 if (visited[nx][ny]) { continue; } dfs(nx, ny); } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') { sx = i; sy = j; } if (maze[i][j] == 'E') { ex = i; ey = j; } } } dfs(sx, sy); if (found) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }这里使用从0开始的行号和列号。
4. 代码里的continue是什么意思？
在迷宫中，我们经常发现某个方向不能走。
if (maze[nx][ny] == '#') { continue; }continue的意思是：跳过本次循环，继续检查下一个方向。
例如，当前位置的上方是墙壁，就不再探索上方，直接检查下方。
它不会结束整个 DFS，只是放弃当前这个方向。
5. 一个重要的细节：找到终点后，为什么还会返回？
在这份程序中，找到终点时：
found = true; return;只是结束当前这一层dfs函数。
如果更深层的函数已经返回了，上一层函数可能还会继续检查其他方向。对于本题而言，这不影响最终的YES或NO。
如果想找到终点后立即结束全部搜索，可以在递归调用后增加判断：
dfs(nx, ny); if (found) { return; }这样，一旦找到终点，就会逐层返回，不再探索其他分支。
第六站：典型例题二——数一数，从起点能到达多少个格子
刚才的任务只需要判断能否找到出口。
现在，我们把任务升级一下。
题目背景
还是一座由道路和墙壁组成的迷宫。现在不需要寻找出口，而是要计算：
从起点出发，不穿过墙壁，最多能到达多少个格子？
起点本身也算一个格子。
1. 算法思路
这次不需要found变量，因为我们不关心是否到达某个终点。
每当 DFS 第一次进入一个可通行的格子：
把它标记为访问过；
计数器加 1；
继续探索四个方向。
注意，计数必须放在标记访问之后，而且每个格子只能计数一次。
2. 参考程序
输入格式与上一题相同，地图中使用S表示起点、#表示墙壁、.表示道路。
#include <iostream> using namespace std; const int N = 105; int n, m; char maze[N][N]; bool visited[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int sx, sy; int cnt = 0; void dfs(int x, int y) { visited[x][y] = true; cnt++; 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 (maze[nx][ny] == '#') { continue; } if (visited[nx][ny]) { continue; } dfs(nx, ny); } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') { sx = i; sy = j; } } } dfs(sx, sy); cout << cnt << endl; return 0; }3. 和上一题有什么区别？
内容 | 迷宫找出口 | 统计可到达格子 |
|---|---|---|
主要目标 | 判断能否到达终点 | 统计可到达的格子数量 |
计数变量 | 不需要 | 需要 |
到达终点后 | 可以停止搜索 | 还要继续探索 |
DFS 的核心 | 标记、检查、深入 | 标记、计数、深入 |
你会发现，DFS 的主体结构几乎不变，改变的往往只是“进入一个新位置后，要完成什么任务”。
这就是算法根据实际需要的变化。
第七站：典型例题三——统计迷宫中有多少个独立区域
题目背景：魔法岛屿地图
魔法王国有一张岛屿地图：
.表示陆地；#表示海洋；上、下、左、右相邻的陆地属于同一块区域；
斜对角相邻不算连接。
请统计地图中有多少块互相分离的陆地区域。
例如：
..##. ..##. ####. .#... .#..#1. 从一块陆地出发，探索整个区域
我们从左上角的陆地出发，使用 DFS 把所有与它连通的陆地都访问一遍。
完成后，这一整块区域就处理完了。
然后继续从左到右、从上到下扫描地图。
如果遇到一块还没有访问过的陆地，说明我们发现了一个新的区域：
区域数量加 1；
从这块陆地开始 DFS；
标记它能够到达的所有陆地。
重复这个过程，直到扫描完整张地图。
2. 算法关键点
与前两题相比，这次多了一层循环：
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 发现没有访问过的陆地 // 区域数加 1 // 从这里启动 DFS } }外层循环负责发现新的区域，DFS 负责把一个区域完整探索出来。
3. 参考程序
#include <iostream> using namespace std; const int N = 105; int n, m; char a[N][N]; bool visited[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void dfs(int x, int y) { visited[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 (a[nx][ny] == '#') { continue; } if (visited[nx][ny]) { continue; } dfs(nx, ny); } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } int regions = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == '.' && !visited[i][j]) { regions++; dfs(i, j); } } } cout << regions << endl; return 0; }对于上面给出的地图，程序输出：
34. 这道题带给我们的新知识
这是一类非常重要的图论问题：连通区域计数。
以后我们遇到：
数地图上的岛屿；
统计森林中相互分离的林地；
统计图中有多少个连通分量；
统计棋盘上互相连接的同色区域；
都可以考虑类似的 DFS 思路。
不过，要注意“连接”的定义：本题只允许上下左右四个方向。如果题目允许斜对角连接，就需要把方向数组扩展为八个方向。
第八站：典型例题四——寻找从起点到终点的一条路径
前面我们知道了“能不能到达终点”，但如果题目要求输出具体的路线，该怎么办？
这次，我们要让探险家留下脚印。
1. 核心想法：记录每一步走到了哪里
我们可以用两个数组记录当前路径：
int pathX[10005]; int pathY[10005]; int pathLen = 0;每次进入一个新格子，就把坐标放入路径数组。
如果成功到达终点，数组里保存的就是一条找到的路线。
如果当前方向走不通，需要回退，就把刚才的格子从当前路径中移除。
这里要特别区分：
visited：记录哪些格子已经探索过，避免重复搜索。pathX、pathY：记录当前这条路线经过了哪些格子。
两者不是一回事。
2. 为什么回退时要恢复路径？
假设当前路线是：
A → B → D
后来发现 D 走不通，就要退回 B，尝试另一条路：
A → B → E
这时，当前路径应该删除 D，再加入 E。
如果不删除 D，路径记录就会变成错误的：
A → B → D → E
但探险家实际上并没有从 D 直接走到 E。
这就是搜索中非常重要的思想：当前路线改变时，路线记录也要跟着改变。
3. 参考程序：找到一条迷宫路径
仍然使用S、E、.、#表示迷宫。
#include <iostream> using namespace std; const int N = 105; int n, m; char maze[N][N]; bool visited[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int sx, sy, ex, ey; int pathX[N * N], pathY[N * N]; int pathLen = 0; bool found = false; void dfs(int x, int y) { visited[x][y] = true; // 把当前格子加入路径 pathX[pathLen] = x; pathY[pathLen] = y; pathLen++; if (x == ex && y == ey) { found = true; return; } 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 (maze[nx][ny] == '#') { continue; } if (visited[nx][ny]) { continue; } dfs(nx, ny); if (found) { return; } } // 当前格子无法通向终点： // 从当前路径中撤销它 pathLen--; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') { sx = i; sy = j; } if (maze[i][j] == 'E') { ex = i; ey = j; } } } dfs(sx, sy); if (!found) { cout << "NO" << endl; } else { cout << "YES" << endl; for (int i = 0; i < pathLen; i++) { cout << "(" << pathX[i] << "," << pathY[i] << ")" << endl; } } return 0; }这里需要特别说明的细节：
这份程序在失败回退时，只恢复pathLen，并没有把visited恢复为false。这是因为它采用的是“每个格子只探索一次”的搜索方式，目标是找到一条可行路线，而不是枚举所有路线。
对于普通的无权迷宫，这种写法能够找到一条可行路径，但不能保证找到步数最少的路径。如果题目要求最短路，通常应该考虑 BFS。
如果题目要求枚举所有不同的简单路径，或者路径中的某个位置允许在不同路线里反复尝试，那么访问标记的恢复方式就需要重新设计。我们后面会专门学习这种“回溯”。
第九站：典型例题五——DFS 还能用来生成所有排列吗？
现在，我们从迷宫转向另一个经典问题。
故事背景：三位勇士的出场顺序
王国要举行庆典，A、B、C 三位勇士需要依次出场。
每位勇士只能出场一次。请输出所有可能的出场顺序。
例如：
ABC
ACB
BAC
还会有哪些呢？
1. 为什么这也是 DFS？
我们可以把每一次选择想象成走进一个新的岔路口。
第一步：选择第一位出场的勇士。
有 A、B、C 三种选择。
如果第一位选择 A，第二位只能从 B、C 中选择。
如果第二位选择 B，第三位就只能选择 C。
这样就得到 ABC。
之后回退到第二位的位置，尝试 C，就得到 ACB。
当第一位的所有方案都尝试完后，再回退到第一位，选择 B。
这就是 DFS 搜索树的思想。
2. 用used数组避免重复使用
bool used[4]; char person[4] = {'A', 'B', 'C'}; char ans[4];used[i]表示第i位勇士是否已经被安排出场。
当我们选择一位勇士时：
used[i] = true;完成后回退：
used[i] = false;注意，这里与之前迷宫的visited不完全一样。
在排列问题中，同一个勇士可以出现在不同的排列里，只是不能在同一个排列里重复出场。因此，回退时必须把used[i]恢复为false。
3. 完整 C++ 参考程序
#include <iostream> using namespace std; char person[3] = {'A', 'B', 'C'}; char ans[3]; bool used[3]; void dfs(int step) { // 三个位置都安排好了 if (step == 3) { for (int i = 0; i < 3; i++) { cout << ans[i]; } cout << endl; return; } // 尝试把每一位勇士放到当前的位置 for (int i = 0; i < 3; i++) { if (used[i]) { continue; } ans[step] = person[i]; used[i] = true; dfs(step + 1); // 回退：把勇士还回去 used[i] = false; } } int main() { dfs(0); return 0; }输出：
ABC ACB BAC BCA CAB CBA一共 6 种排列。
为什么是 6 种？
第一位有 3 种选择，第二位有 2 种，第三位有 1 种，所以：
3 * 2 * 1 = 6
也就是：
3! = 6
4. 这道题教会我们的重要知识
DFS 不只是走迷宫，还可以枚举所有可能的方案。
排列问题的通用思路是：
确定当前要填写的位置。
枚举所有可以放进去的元素。
标记元素已经使用。
递归填写下一个位置。
返回时撤销标记，尝试其他元素。
这就是回溯搜索的基本形态。后面的 DFS 单元会继续深入学习如何保存状态、撤销选择以及剪枝。
第十站：典型例题六——从 1 走到 n，一共有多少条不同的路径？
这道题用来练习 DFS 的递归过程与计数。
题目背景
有一条简单的数字通道，起点是 1。每一步只能从当前数字走到：
当前数字加 1；
当前数字加 2。
例如，从 1 走到 4，可以有：
1 → 2 → 3 → 41 → 2 → 41 → 3 → 4
请问，从 1 走到n一共有多少种走法？
这里的路径只看经过的数字序列。
1. DFS 思路
假设当前在数字x：
如果
x == n，说明找到了一条完整路径，答案加 1。如果
x > n，说明走过头了，这条路线无效。否则尝试走到
x + 1。再尝试走到
x + 2。
每条完整路线都会被枚举一次。
2. 参考程序
#include <iostream> using namespace std; int n; long long ans = 0; void dfs(int x) { if (x == n) { ans++; return; } if (x > n) { return; } dfs(x + 1); dfs(x + 2); } int main() { cin >> n; dfs(1); cout << ans << endl; return 0; }输入：
4输出：
33. 为什么这题不需要visited？
因为我们不是在一张有环的地图里反复访问顶点，而是在一个不断增大的数字序列中搜索。
每一步都从x走向更大的数字，因此不可能回到之前的数字，也不会形成循环。
不过，这份程序枚举了所有走法，随着n增大，搜索量会迅速增加。更大的数据通常适合用动态规划求解。
这也是算法学习的重要一环：DFS 可以帮助我们理解所有方案，但当方案数量太多时，就要考虑更高效的方法。
第十一站：变式训练——同一个 DFS，换一个任务
现在我们来做几道变式题。它们不一定都需要完整的复杂代码，重点是训练你从题目中识别 DFS 的核心结构。
变式一：数一数能走到多少个格子
在一个二维地图中，.表示道路，#表示墙壁。给定起点，统计起点所在连通区域的大小。
提示：使用visited数组；每次首次进入一个道路格子时，计数加 1。
变式二：统计独立岛屿
地图中1表示陆地，0表示海洋。上下左右相连的陆地属于同一座岛屿，求岛屿数量。
提示：扫描整个地图，发现一个未访问的1，就启动一次 DFS，岛屿数量加 1。
变式三：输出所有二进制串
给定整数n，输出所有长度为n的二进制串。例如n = 2时，输出00、01、10、11。
提示：每个位置有两种选择：填写 0 或填写 1。填完所有位置就输出。
变式四：从 1 到 n，只能加 1 或加 3
每一步只能把当前数字增加 1 或增加 3，问从 1 到 n 有多少种走法。
提示：递归尝试dfs(x + 1)和dfs(x + 3)；到达 n 时计数，超过 n 时返回。
变式五：三位密码
用数字 1、2、3 组成三位密码，每个数字最多使用一次，输出所有可能的密码。
提示：与三位勇士排列问题相同，使用used数组和递归位置step。
这些题目的故事不同，但它们有一个共同点：每一步做出一个选择，然后继续探索剩下的可能性。
第十二站：复杂度分析——DFS 会不会搜索到天荒地老？
DFS 的优点是思路清晰，代码结构也很自然。但它并不总是快。
搜索速度主要取决于两个因素：
搜索过程中会访问多少个状态或顶点？
每个状态需要检查多少个后续选择？
1. 图的 DFS：每个顶点访问一次
对于使用邻接表存储的图，如果从一个起点开始搜索，且每个顶点最多访问一次：
每个顶点最多被访问一次；
每条边最多被检查常数次。
因此，完整遍历图的时间复杂度为：
O(V+E)
其中：
V 表示顶点数量；
E 表示边的数量。
例如，一张有 100 个顶点、200 条边的图，DFS 只需要处理这些顶点和边，不需要枚举所有顶点的排列。
2. 二维网格 DFS：每个格子访问一次
如果地图有 n 行、m 列，每个格子最多访问一次，每次最多检查四个方向，那么时间复杂度是：
O(nm)
因为总共有 n * m 个格子。
3. 排列问题：搜索量可能非常大
如果我们要生成 n 个不同元素的所有排列，那么方案数为：
n!
仅输出所有排列，就需要与 n! 成正比的时间。若每个排列都要输出 n 个元素，总时间通常为：
O(n * n!)
当 n 变大时，排列数量会迅速增长。
例如：
元素个数 \(n\) | 排列数量 \(n!\) |
|---|---|
3 | 6 |
5 | 120 |
8 | 40,320 |
10 | 3,628,800 |
12 | 479,001,600 |
所以，枚举排列适合较小规模的数据。对于大规模搜索，我们往往需要剪枝、动态规划或其他优化。
4. DFS 的空间复杂度
DFS 还会使用递归调用栈。
如果搜索的最大递归深度是 d ，递归栈通常需要 O(d) 的空间。
此外，程序还可能保存visited数组、地图、邻接表或当前路径。这些数据也要计入总空间复杂度。
例如：
图的邻接表与访问数组：通常需要 O(V+E) 空间；
二维地图与访问数组：通常需要 O(nm)空间；
排列搜索的递归深度：通常为 O(n) ，另有用于记录答案的数组。
特别提醒： 即使时间复杂度允许，递归深度过大也可能导致栈溢出。对于很深的图或长链，有时需要使用显式栈来模拟 DFS。
第十三站：DFS 初学者最容易犯的六个错误
同学们，很多时候，DFS 的思路并不难，真正让程序出错的是一些小细节。
我们来看看六个常见陷阱。
错误一：没有设置递归结束条件
函数一直调用自己，可能导致栈溢出。
改进：明确什么时候到达目标、什么时候走不通，以及什么时候应该返回。
错误二：忘记标记已经访问的顶点
在有环的图中，程序可能反复访问同一批顶点。
改进：普通图遍历中，进入顶点后及时标记visited[x] = true。
错误三：把越界判断放得太晚
访问maze[nx][ny]之前，没有确认坐标合法。
改进：先检查边界，再访问数组。
错误四：把visited和当前路径混为一谈
它们分别记录“已经探索过什么”和“当前路线经过什么”。在排列、组合等回溯问题中，通常需要撤销当前选择。
改进：根据题目判断，回退时应该恢复哪些状态。
错误五：以为 DFS 找到的路径一定最短
DFS 优先深入，不保证先找到的路径最短。
改进：无权图的最短路通常优先考虑 BFS。
错误六：搜索规模太大，仍然直接枚举
例如生成 15 个元素的所有排列，方案数已经非常庞大。
改进：估算搜索规模，必要时使用剪枝、动态规划或其他算法。
第十四站：课堂自测——看看你是否真正理解了 DFS
1. 深度优先搜索最重要的特点是什么？
先访问离起点最近的所有顶点
沿着一条分支不断深入，必要时回退
每次选择数字最大的顶点
答案：B
DFS 的核心是深入一条分支，无法继续时再回退。
2. 在普通图 DFS 中，visited 数组的主要作用是什么？
记录顶点的权重
记录顶点是否已经访问，避免重复探索
记录所有最短路径
答案：B
它能避免在有环的图中反复进入同一顶点。
3. 一个有 4 个顶点的树，从根开始按左子树优先 DFS。根的左孩子为 B、右孩子为 C，B 的孩子为 D、E。访问顺序应为？
A B D E C
A B C D E
A C B E D
答案：A
先访问根 A，再深入左子树 B、D、E，最后访问右子树 C。
4. 为什么排列 DFS 在回退时要把 used[i] 恢复为 false？
为了让其他分支也能使用这个元素
为了让程序提前结束
为了让排序更快
答案：A
一个元素不能在同一个排列中重复，但可以出现在其他排列里。
5. 对一个使用邻接表存储的图进行完整 DFS，时间复杂度通常是多少？
O(V+E)
O(V²) 必然成立
O(V!)
答案：A
每个顶点访问一次，每条边被检查常数次
编程作业：魔法迷宫挑战
请同学们完成下面三道递进题目。
作业一：能不能走出去？
给定一个迷宫，S是起点，E是终点，#是墙，.是道路。每次只能上下左右移动，判断能否到达终点。
考查：二维数组、方向数组、DFS、访问标记。
作业二：统计魔法岛屿
地图中1表示陆地，0表示海洋。上下左右相邻的陆地属于同一个岛屿。请统计岛屿数量。
考查：双重循环、连通区域、重复调用 DFS。
作业三：勇士密码排列
给定数字1、2、3、4，每个数字最多使用一次，输出所有四位排列。
考查：递归层数、used 数组、回退恢复、搜索树。
本单元总结：带走你的 DFS 探险工具箱
今天，我们从魔法迷宫出发，学习了 DFS 的核心思想，并通过多道例题认识了它的不同用途。
DFS 基础模板
void dfs(int x) { // 1. 判断是否到达目标 // 2. 标记当前状态 // 3. 枚举下一步的所有选择 // 4. 检查选择是否合法 // 5. 递归探索 // 6. 必要时撤销当前选择 }这是思路模板，不是可以直接运行的完整程序。不同题目需要补充不同的状态、条件与回退操作。
本单元的六个核心知识点
DFS：沿着一条分支深入，无法继续时回退。
递归：函数调用自己，返回时回到上一层。
visited：记录已经探索过的状态，避免重复访问。方向数组：用
dx、dy统一枚举上下左右。搜索树：把每一次选择看作进入一个新的分支。
回溯：撤销当前选择，让其他分支也能尝试。
最后，请同学们记住这句口诀：
先判断，再标记；枚举选择，递归深入；走不通时回退，换条道路再探索。
下一单元，我们将继续深入 DFS：学习搜索树与递归的完整推演、如何记录当前路径，以及如何枚举所有方案。届时，我们会从简单排列逐步走向组合、子集和更复杂的回溯问题，让 DFS 真正成为你解决算法题的利器。
)