第 40 课：深度优先搜索
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索图或树（图和树的知识在第 10 章讲解）结构的算法。
在生活中，我们也会直接或间接使用到深度优先搜索。比如在路径规划方面，它能帮助导航软件规划路线；在游戏领域，它可解决迷宫问题、辅助棋类游戏决策；在资源管理上，它可用于文件系统遍历；在社交网络分析中，它能查找人脉关系、分析信息传播路径等。
现在我们跟随蛙蛙进入迷宫场景中，深入了解深度优先搜索。
40.1 情景引入及建模
走迷宫场景演示
蛙蛙被困在一个 3 × 3 的迷宫中，迷宫的左上角是起点，右下角是迷宫出口（用 exit 表示）。迷宫中有些格子是 0，表示不可通行（可能是沼泽或岩石），其他格子是 1，表示可以安全落脚，如表 9-1 所示。
蛙蛙每次只能向上、下、左、右四个方向移动一格，且不能重复走过任何格子，蛙蛙有多少种不同的路径可以成功逃出迷宫呢？
表 9-1 蛙蛙所在的迷宫
| 蛙蛙 | 1 | 0 |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | exit |
如何移动？
如果已经到达终点，则表示多了一条可以到达终点的路径。
每次可以选择移动到的格子有当前点的上、下、左、右四个方向的格子。
按照顺序尝试每个格子是否可走，如果格子不在迷宫中或者遇到沼泽或岩石，则不能走。
找到第一个可以走的格子（比如往上走一格），则标记该格子，表示已经走过。
再从新的格子出发，重复上述过程（递归进行）。
将刚才遍历的格子消除标记，再尝试从之前格子的其他方向出发去找路线。
问题建模
如何表示迷宫地图等信息呢？
我们可以使用一个 3 × 3 的二维数组 maze 来存储迷宫信息，如果值为 0 表示不可走，1 表示可走，如表 9-2 所示。
表 9-2 用二维数组 maze 来存储迷宫信息
| 1 | 1 | 0 |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | 1 |
再使用一个 3 × 3 的二维数组 used 来标记是否走过某个格子，没走过为 0，走过为 1，如表 9-3 所示。
表 9-3 用二维数组 used 来标记是否走过某个格子
| 0 | 0 | 0 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 0 |
刚开始时，由于蛙蛙还没有走，所以所有元素初始化为 0。若蛙蛙已经走了迷宫中第 1 行第 2 列的格子，则需要将这个格子标记为 1，即 used[1][2] = 1，表示 maze[1][2] 已经走过。
目前蛙蛙在左上角，即第 1 行第 1 列的位置。现在蛙蛙要开始移动了，又该如何表示每次移动的过程呢？每次移动，实际上就是坐标的变化。假设蛙蛙在中间位置 (2, 2)，如表 9-4 所示。
表 9-4 蛙蛙所在的位置
| 0 | 0 | 0 |
|---|---|---|
| 0 | 蛙蛙 | 0 |
| 0 | 0 | 0 |
若蛙蛙向上走，来到位置 (1, 2)，相对于当前位置 (2, 2) 行坐标 −1，列坐标不变。
若蛙蛙向下走，来到位置 (3, 2)，相对于当前位置 (2, 2) 行坐标 +1，列坐标不变。
若蛙蛙向左走，来到位置 (2, 1)，相对于当前位置 (2, 2) 行坐标不变，列坐标 −1。
若蛙蛙向右走，来到位置 (2, 3)，相对于当前位置 (2, 2) 行坐标不变，列坐标 +1。
遍历方向
我们可以用一个 4 行 2 列的二维数组 fx 保存能够一步到达的四个方向，为了方便描述，我们按顺时针方向，从上方开始，即上、右、下、左的顺序，如表 9-5 所示。
表 9-5 每一步的四种走法及坐标变化
| 每一步的走法 | x 坐标的变化 | y 坐标的变化 |
|---|---|---|
| 向上走，行 −1，列不变 | −1 | 0 |
| 向右走，行不变，列 +1 | 0 | 1 |
| 向下走，行 +1，列不变 | 1 | 0 |
| 向左走，行不变，列 −1 | 0 | −1 |
代码如下：
int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};假设当前坐标为 (2, 2)，向上移动就是 (2 + fx[0][0], 2 + fx[0][1])，即来到坐标 (2 + (−1), 2 + 0) = (1, 2) 的位置。
可以通过 for 循环遍历四个方向：
for (int i = 0; i < 4; i++) // 尝试上、右、下、左四个方向
{
int nx = x + fx[i][0]; // 新的 x 坐标 nx
int ny = y + fx[i][1]; // 新的 y 坐标 ny
}完整代码及解析
#include <iostream>
using namespace std;
int ans = 0, maze[6][6], used[6][6], fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void dfs(int x, int y)
{
if (x == 3 && y == 3) // 如果当前找的点就是终点，则方案数+1，结束本次搜索
{
ans++;
return;
}
else
{
used[x][y] = 1; // 将当前所在的点标记为 1，表示走过
for (int i = 0; i < 4; i++) // 尝试上、下、左、右四个方向
{
int nx = x + fx[i][0];
int ny = y + fx[i][1]; // 下一次查找的点的坐标 nx，ny
// (nx,ny)要在地图内，可走，并且未被走过
if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3 && used[nx][ny] == 0 && maze[nx][ny] == 1)
{
used[nx][ny] = 1; // 表示 (nx,ny)走过
dfs(nx, ny); // 从(nx,ny)再去找
used[nx][ny] = 0; // 消除标记，再尝试其他方向
}
}
used[x][y] = 0; // 消除标记
}
}
int main()
{
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
cin >> maze[i][j];
}
}
dfs(1, 1); // 从左上角出发
cout << ans; // 输出最终方案数
return 0;
}运行后输入：
1 1 0
1 1 1
1 1 1运行结果：
740.2 深度优先搜索模板
走迷宫的过程就是一个深度优先搜索的过程：从可以解决问题的某一个方向出发，一直深入寻找，找到这个方向可以得到的所有解决方案；如果找不到，则回退到上一步，从另一个方向开始，再次深入寻找。
注意事项
我们在使用深度优先搜索解决问题时要注意：
首先弄清楚问题的解空间，即迷宫有多大；
弄清楚搜索的边界，即到哪一步就该停下，不用再搜；
搜索的方向，即可能包含哪几种问题。
模板
void dfs() // 深度优先搜索
{
if (到达终点状态)
{
... // 根据题意添加
return;
}
if (越界或者是不合法状态)
return;
if (特殊状态) // 剪枝
return;
for (所有可能的下一个状态)
{
if (状态符合条件)
{
修改操作; // 根据题意来添加
标记;
dfs();
// 根据题意看是否需要还原标记，这种方法称为回溯法
}
}
}40.3 实例讲解
例 1：迷宫
有一个 N × M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
给定起点坐标和终点坐标，规定每个格子最多经过 1 次，问有多少种从起点坐标到终点坐标的方案。
在迷宫中移动有上、下、左、右四种方式，每次只能移动一个格子，数据保证起点上没有障碍。
【输入格式】输入 T + 2 行。
第 1 行输入 3 个正整数 N、M 和 T，N 为行、M 为列、T 为障碍总数。
第 2 行输入 4 个正整数：起点坐标 SX、SY，终点坐标 FX、FY。
接下来 T 行，每行为障碍点的坐标。
【输出格式】输出一行，为给定起点坐标和终点坐标，每个格子最多经过 1 次，从起点坐标到终点坐标的方案总数。
【输入样例】
2 2 1
1 1 2 2
1 2【输出样例】
1【数据范围】1 ≤ N ≤ 20，1 ≤ M ≤ 20，0 ≤ T ≤ N × M − 2，起点无障碍。
解析
从起点出发，尝试向四个方向移动。
每次移动时标记当前格子为已访问，避免重复访问。
到达终点时，路径数 ans 加 1。
回溯时取消标记，以便探索其他路径。
参考代码
#include <iostream>
using namespace std;
int ans = 0, maze[21][21], used[21][21];
int Fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m, t, sx, sy, fx, fy, tx, ty;
// 深度优先搜索
void dfs(int x, int y, int s, int e)
{
if (x == s && y == e) // 如果到达终点
{
ans++; // 路径数+1
return;
}
else
{
used[x][y] = 1; // 标记当前格子为已访问
for (int i = 0; i < 4; i++) // 尝试四个方向
{
int nx = x + Fx[i][0]; // 计算下一个格子的 x 坐标
int ny = y + Fx[i][1]; // 计算下一个格子的 y 坐标
// 检查是否越界、未访问且无障碍
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && used[nx][ny] == 0 && maze[nx][ny] == 0)
{
used[nx][ny] = 1; // 标记下一个格子为已访问
dfs(nx, ny, s, e); // 递归搜索
used[nx][ny] = 0; // 回溯，取消标记
}
}
used[x][y] = 0; // 回溯，取消当前格子的标记
}
}
int main()
{
// 输入迷宫基本信息
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
// 初始化迷宫（默认所有格子可通行）
for (int i = 1; i <= t; i++)
{
cin >> tx >> ty;
maze[tx][ty] = 1; // 标记障碍物
}
// 从起点开始深度优先搜索
dfs(sx, sy, fx, fy);
// 输出路径总数
cout << ans;
return 0;
}例 2：全排列问题
排列是指从给定的元素集合中选取部分或全部元素，按照一定顺序进行排列的方式。
现在数学老师希望蛙蛙能够编写一个程序，帮忙解决数学中的排列问题，要求能够根据用户输入的整数 n（需满足 n ≤ 9），输出从 1 到 n 这 n 个数字的所有不同排列方式。
例：n = 3，全排列为 123、132、213、231、312、321。
【输入格式】输入一行，一个正整数 n。
【输出格式】输出若干行，为 1 到 n 的数的全排列（n ≤ 9），按照字典序（若第一个数相同，则比较第二个数，以此类推）从小到大换行输出。
【输入样例】
3【输出样例】
123
132
213
231
312
321注：原书输出样例中 321 排在 312 之前，与字典序及书中解析（"得到 312 和 321"）不符，疑为原书排版笔误，此处已按字典序修正。
解析
样例分析
输入 3，第一个数从 1 开始尝试：
| 1 |
|---|
第二个数继续从 1 开始尝试，由于 1 已经被使用，继续尝试 2：
| 1 | 2 |
|---|
第三个数继续从 1 开始尝试，由于 1 已经被使用，继续尝试 2，也被使用，继续尝试 3：
| 1 | 2 | 3 |
|---|
得出第一个数 123，接着回溯到第二个数，可以尝试 3：
| 1 | 3 |
|---|
再接着往后，第三个数继续从 1 开始尝试，由于 1 已经被使用，继续尝试 2：
| 1 | 3 | 2 |
|---|
得出第二个数 132，接着加 1，发现 3 已经被使用过，回溯到第一个数，从 2 开始继续尝试：
| 2 |
|---|
按上述步骤，得出 213 和 231，再回溯到第一个数从 3 开始出发，得到 312 和 321。
最终输出 123、132、213、231、312、321 这六个数。
我们可以采用深度优先搜索，通过递归的方式，逐步构建上述过程，在构建过程中记录已经使用过的数字，避免重复使用，直至得到完整的排列。
通过 ans 数组存储当前正在构建的排列。通过 used 数组进行标记，used[i] 若为 1，表示数字 i 已在当前排列中被使用；若为 0，则表示未被使用。
通过 for 循环遍历从 1 到 n 的所有数字。
若数字 i 未被使用（used[i] 为 0），则将其放入 ans 数组的第 x 个位置，同时标记 used[i] 为 1，表示该数字已被使用。
递归调用 dfs(x + 1, n)，继续构建下一个位置的数字。
递归返回后，将 used[i] 重置为 0，这是回溯操作，目的是撤销之前的选择，以便尝试其他可能的排列。
当 x 大于 n 时，意味着已经成功构建了一个完整的排列（ans 数组中存储了 1 到 n 的一个排列），此时将该排列输出并换行，然后返回。
参考代码
#include <iostream>
using namespace std;
int ans[10], used[10];
// x 表示当前要填充排列的第 x 个位置，n 表示排列的总长度
void dfs(int x, int n)
{
// 当 x 大于 n 时，说明已经成功生成了一个完整的排列
if (x > n)
{
// 遍历 ans 数组，输出当前生成的排列
for (int i = 1; i <= n; i++)
cout << ans[i];
cout << endl;
// 结束当前递归调用，返回上一层
return;
}
// 尝试将 1 到 n 中的每个数字填入当前位置
for (int i = 1; i <= n; i++)
{
// 如果数字 i 还未被使用
if (!used[i])
{
// 将数字 i 填入排列的第 x 个位置
ans[x] = i;
// 标记数字 i 已被使用
used[i] = 1;
// 递归调用 dfs 函数，填充下一个位置
dfs(x + 1, n);
// 回溯操作，将数字 i 标记为未使用，以便尝试其他可能的排列
used[i] = 0;
}
}
}
int main()
{
int n;
cin >> n;
// 调用 dfs 函数，从排列的第一个位置开始填充
dfs(1, n);
return 0;
}例 3：棋盘的马
蛙蛙最近拿到一个特殊的象棋棋盘，这个棋盘可以看作一个由坐标点构成的网格，棋盘的左下角位置为坐标 (0, 0)，而右上角位置为坐标 (m, n)，这里的 m 和 n 均为非负整数。
马在棋盘上移动时有着特殊的规则：它只能向右移动，不能向左移动。
也就是说，在它移动过程中的任意一步，它的横坐标不会减小。每次移动时，马遵循国际象棋中马的移动规则，即"日"字形移动。具体而言，马从当前位置 (x, y) 出发，可以移动到以下 4 个位置之一（由于只能向右移动，所以会排除掉向左的移动方向）：
- (x + 1, y + 2)
- (x − 1, y + 2)
- (x + 2, y + 1)
- (x − 2, y + 1)
需要注意的是，马的移动不能超出棋盘的边界，即移动后的位置 (nx, ny) 需满足 0 ≤ nx ≤ m 且 0 ≤ ny ≤ n。
蛙蛙准备编写一个程序，计算这匹马从棋盘左下角 (0, 0) 出发，按照上述规则移动到右上角 (m, n) 总共存在多少条不同的路径，并准备将这个路径总数打印输出。
【输入格式】输入一行，两个整数 m 和 n（m ≤ 20，n ≤ 20）。
【输出格式】输出一行，为马从棋盘左下角到右上角的方法总数。
【输入样例】
3 3【输出样例】
2解析
样例分析
马在棋盘上只能向右移动，每次移动遵循国际象棋中"日"字形的规则。
符合要求的移动方向有 (x + 1, y + 2)、(x + 2, y + 1)、(x − 1, y + 2)、(x − 2, y + 1)，同时移动后的位置 (nx, ny) 需要满足 0 ≤ nx ≤ m 且 0 ≤ ny ≤ n。下面以 3 × 3 的棋盘为例分析马移动的路径。
- 路径 1
a. 第一步：从 (0, 0) 出发，按照 (x + 2, y + 1) 的规则移动，得到新位置为 (0 + 2, 0 + 1) = (2, 1)。
b. 第二步：从 (2, 1) 出发，按照 (x + 1, y + 2) 的规则移动，得到新位置为 (2 + 1, 1 + 2) = (3, 3)。
- 路径 2
a. 第一步：从 (0, 0) 出发，按照 (x + 1, y + 2) 的规则移动，得到新位置为 (0 + 1, 0 + 2) = (1, 2)。
b. 第二步：从 (1, 2) 出发，按照 (x + 2, y + 1) 的规则移动，得到新位置为 (1 + 2, 2 + 1) = (3, 3)。
所以在这个 3 × 3 的棋盘里，从 (0, 0) 移动到 (3, 3)，马依据只能向右移动的"日"字形规则，仅有上述两条不同的移动路径。
参考代码
#include <iostream>
using namespace std;
int ans, m, n;
// 存储马的四个可能移动方向
int fx[4][2] = {{-2, 1}, {2, 1}, {1, 2}, {-1, 2}};
// 探索马的移动路径
void dfs(int x, int y)
{
// 当马移动到目标位置 (m, n) 时
if (x == m && y == n)
{
ans++; // 方案数加 1
return;
}
for (int i = 0; i < 4; i++) // 尝试四个方向
{
int nx = x + fx[i][0]; // 新的 x 坐标
int ny = y + fx[i][1]; // 新的 y 坐标
// (nx,ny)要在棋盘内
if (nx >= 0 && nx <= m && ny >= 0 && ny <= n)
dfs(nx, ny);
}
}
int main()
{
cin >> m >> n;
dfs(0, 0); // 从左下角出发
cout << ans;
return 0;
}