迷宫问题表面上是在二维网格中找路，本质上是图的遍历：每个可通行格子是顶点，相邻可达格子之间存在边。使用栈或递归进行深度优先搜索，可以寻找任意可行路径；使用队列进行广度优先搜索，则能在无权网格中找到步数最少的路径。
1. 把迷宫建模成图
设迷宫是 $m\times n$ 的网格：
0 表示可通行；1 表示墙；- 每个可通行格子
(row, col) 是一个顶点；
- 若两个格子上下左右相邻且都可通行，就在它们之间连边。
四个方向可以统一写成：
1
2
| constexpr int DR[4] = {-1, 1, 0, 0};
constexpr int DC[4] = {0, 0, -1, 1};
|
考察邻居 (nr, nc) 时必须依次检查：
- 是否在边界内；
- 是否可通行；
- 是否已经访问。
先检查边界，再访问数组，否则会产生越界和未定义行为。
2. 为什么需要 visited
网格中的边通常是双向的：从 A 能走到 B，也能立刻从 B 返回 A。如果不记录访问状态，搜索可能在两个格子之间无限循环。
常见策略有：
- 单独维护
visited[m][n]；
- 在允许修改输入时，把已访问格子标记成特殊值；
- 维护“本次路径中是否出现”的标记，用于需要枚举所有简单路径的回溯问题。
“全局访问过”和“当前路径使用中”语义不同。只寻找一条路径或最短路时通常使用全局 visited；枚举全部路径时，回溯离开格子后往往要撤销当前路径标记。
3. DFS：沿一条路走到底
深度优先搜索（DFS）从当前位置选择一个未访问邻居继续深入；走到死路时退回最近的分叉点尝试其他方向。
递归版本的结构为：
1
2
3
4
5
6
7
| dfs(current):
若 current 是出口，返回成功
标记 current 已访问
对每个合法且未访问的邻居 next：
记录 next 的父节点为 current
若 dfs(next) 成功，向上传递成功
返回失败
|
递归调用栈隐式保存了回退位置。也可以显式使用栈，以避免递归过深导致调用栈溢出。
3.1 DFS 能保证什么
DFS 能在线性时间内判断出口是否可达，并找到一条路径，但在普通无权迷宫中不保证路径最短。它得到哪条路径还会受到方向枚举顺序影响。
若网格共有 $V=mn$ 个格子，每个格子最多检查 4 条边，时间为 $O(V)$，访问数组与递归栈最坏需要 $O(V)$ 空间。
4. BFS：按距离逐层扩展
广度优先搜索（BFS）使用队列：先处理距离起点为 0 的顶点，再处理距离为 1、2、3……的顶点。
1
2
3
4
5
6
| 起点入队并标记访问
while 队列非空：
current 出队
对每个合法且未访问的邻居 next：
标记 next，记录父节点
next 入队
|
4.1 为什么 BFS 能找到最短路
在每条边代价相同的无权图中，队列保证按“从起点经过的边数”非递减顺序扩展节点。某个格子第一次被发现时，不可能存在一条更短但尚未处理的路径，因此首次到达终点的距离就是最短距离。
这个结论有严格前提：每步代价相同。如果进入草地、沙地等格子的代价不同，应使用 Dijkstra；边权只有 0 和 1 时可用 0-1 BFS；启发式搜索场景可考虑 A*。
5. 路径还原
仅记录“访问过”只能判断可达性。若要输出完整路径，应在首次发现节点时记录它来自哪个父节点：
到达终点后，从终点沿 parent 反向追溯至起点，再反转序列，即得到正向路径。
父节点应在节点入队时写入，同时标记访问。如果等到出队才标记，同一节点可能被多个前驱重复入队，增加开销并让父节点语义混乱。
6. 可运行的 BFS 最短路实现
下面的 C++17 程序支持任意起点和终点，返回包含两端点的最短路径；不存在路径时返回空数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
struct Point {
int row;
int col;
};
static bool operator==(Point a, Point b)
{
return a.row == b.row && a.col == b.col;
}
static bool inside(const std::vector<std::vector<int>>& maze, Point p)
{
return p.row >= 0 && p.col >= 0 &&
p.row < static_cast<int>(maze.size()) &&
p.col < static_cast<int>(maze[0].size());
}
static std::vector<Point> shortest_path(
const std::vector<std::vector<int>>& maze, Point start, Point goal)
{
if (maze.empty() || maze[0].empty()) {
return {};
}
const std::size_t cols = maze[0].size();
for (const auto& row : maze) {
if (row.size() != cols) {
return {};
}
}
if (!inside(maze, start) || !inside(maze, goal) ||
maze[start.row][start.col] != 0 || maze[goal.row][goal.col] != 0) {
return {};
}
const int rows = static_cast<int>(maze.size());
const Point none{-1, -1};
std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
std::vector<std::vector<Point>> parent(rows, std::vector<Point>(cols, none));
std::queue<Point> pending;
constexpr std::array<Point, 4> directions{{
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
}};
visited[start.row][start.col] = true;
pending.push(start);
while (!pending.empty()) {
Point current = pending.front();
pending.pop();
if (current == goal) {
break;
}
for (Point direction : directions) {
Point next{current.row + direction.row, current.col + direction.col};
if (inside(maze, next) && maze[next.row][next.col] == 0 &&
!visited[next.row][next.col]) {
visited[next.row][next.col] = true;
parent[next.row][next.col] = current;
pending.push(next);
}
}
}
if (!visited[goal.row][goal.col]) {
return {};
}
std::vector<Point> path;
for (Point p = goal;; p = parent[p.row][p.col]) {
path.push_back(p);
if (p == start) {
break;
}
}
std::reverse(path.begin(), path.end());
return path;
}
int main()
{
const std::vector<std::vector<int>> maze{
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0}
};
const std::vector<Point> path = shortest_path(maze, {0, 0}, {4, 4});
assert(!path.empty());
assert((path.front() == Point{0, 0}));
assert((path.back() == Point{4, 4}));
assert(path.size() == 9);
for (Point p : path) {
std::cout << '(' << p.row << ',' << p.col << ") ";
}
std::cout << '\n';
}
|
这里使用 path.size() - 1 表示步数，因为路径数组同时包含起点和终点。
7. 使用显式栈的 DFS
递归 DFS 写法简洁，但大迷宫可能导致调用栈过深。显式栈版本可以这样组织：
1
2
3
4
5
| 起点入栈并标记
while 栈非空：
current = 栈顶并弹出
若 current 是终点则结束
将未访问邻居标记、记录父节点并压栈
|
如果只想模拟“走一步，死路再退一步”的可视过程，可以让栈保存当前路径：查看栈顶邻居，找到可走方向就压栈；没有邻居时弹栈回退。若只寻找一条路径，到达终点时整个栈就是路径。
8. 枚举所有路径
若要输出起点到终点的所有简单路径，DFS 需要在递归返回时撤销状态：
1
2
3
4
5
| 标记 current 在当前路径中
把 current 加入 path
递归探索每个未在当前路径中的邻居
从 path 删除 current
取消 current 的当前路径标记
|
枚举所有路径的数量可能呈指数增长，因此算法时间不再是简单的 $O(mn)$。输出本身可能就非常大，应设置规模限制或只统计、只找前若干条路径。
9. 带权迷宫与更复杂状态
9.1 不同地形代价
如果每个格子的进入代价不同，普通 BFS 不再保证总代价最小：
- 非负权：Dijkstra；
- 只有 0/1 权：0-1 BFS；
- 有合理启发函数并希望更快到达目标：A*。
9.2 钥匙、门与传送点
当“能否进入格子”取决于已经拿到的钥匙，顶点就不能只用坐标表示。状态应扩展为：
同一个格子携带不同钥匙集合，是图中的不同状态。visited 也必须包含完整状态，否则会错误剪枝。
9.3 多源 BFS
若要求每个格子到最近出口或最近障碍的距离，可以把所有源点同时入队并设距离为 0，再进行一次 BFS。这比从每个格子分别搜索高效得多。
10. 常见错误
- 访问
maze[nr][nc] 后才检查边界；
- 没有
visited，在环中无限往返；
- 认为 DFS 找到的一定是最短路径；
- BFS 到出队时才标记访问，造成重复入队；
- 没有验证起点、终点是否越界或位于墙上；
- 输入网格各行长度不一致；
- 修改迷宫作为访问标记，却忘记调用者仍需要原始网格；
- 只记录距离没有记录父节点，最后无法还原路径；
- 在带权迷宫中仍使用普通 BFS；
- 把路径包含的格子数误当作移动步数。
11. 测试清单
至少覆盖以下情况：
- 起点等于终点；
- 单行、单列和 $1\times1$ 网格；
- 起点或终点是墙；
- 完全无路；
- 存在多条等长最短路；
- 有环和大面积开放区域；
- 路径贴着四条边界；
- 非矩形输入；
- 大网格下的时间与空间；
- 返回路径的每对相邻格子是否真正相邻且可通行。
迷宫题最重要的迁移能力，是把画面抽象为“状态 + 合法转移”。确定图是无权还是带权、需要任意路径还是最短路径，再选择 DFS、BFS 或最短路算法，问题就会从“绕迷宫”转化为标准的图搜索。
