1. 迷宫寻宝类题目的核心解题思路拆解

迷宫寻宝这个题型在算法竞赛里出现的频率相当高，几乎每一本算法入门教材都会把它当作搜索算法的经典案例。我第一次接触这类题目的时候，踩过一个很典型的坑：看到迷宫就想着用动态规划去推，结果发现状态转移根本没法处理“走回头路”和“绕远路拿钥匙再回来开门”这种复杂情况。后来才明白，这类题目本质上是在一个图结构上做状态空间搜索，最稳妥的解法就是广度优先搜索，也就是BFS。

1.1 为什么BFS是迷宫类搜索的首选

先说说BFS和DFS在这类题目里的本质区别。DFS是一条路走到黑，撞墙了再回头，它天然适合判断“有没有解”以及“枚举所有路径”这类问题。但迷宫寻宝通常问的是“最短步数是多少”或者“最少需要多少时间能拿到所有宝物”，这就涉及到一个最优化问题。BFS按层扩展的特性决定了它第一次到达某个状态时，走过的步数一定是最少的。这个性质不是巧合，而是由BFS的队列结构保证的——队列先进先出，所有距离为k的状态一定比距离为k+1的状态先被处理完。

你可以把BFS想象成往水里扔石头后泛起的涟漪，一圈一圈往外扩散，每一圈代表一步。当涟漪第一次碰到目标点时，那个圈数就是最短距离。DFS则像是一根探针往深处扎，扎到目标时你没法保证走的是最短路径，还得把所有路径都枚举出来比较，时间复杂度直接爆炸。

1.2 迷宫寻宝与普通迷宫最短路的差异点

普通迷宫最短路只需要处理“人在哪里”这一个状态维度，但迷宫寻宝往往多了几个维度。最常见的是钥匙和门的机制：地图上有若干把钥匙，对应若干扇门，拿到钥匙才能开门。这时候状态就不只是坐标(x, y)，还得记录“当前已经拿到了哪些钥匙”。钥匙数量少的时候可以用位运算压缩成一个整数，比如有3把钥匙，状态就可以是000到111之间的一个数。

另一个常见变体是宝物收集：地图上散落着若干宝物，要求全部收集后再到达终点。这种题目的状态维度会更高，因为你需要记录“哪些宝物已经收集了”。如果宝物数量不超过10到15个，同样可以用状态压缩来处理。状态空间的大小就是行数×列数×2的宝物数量次方，只要这个乘积在可接受范围内，BFS就能跑。

还有一种变体是带时间限制或者带怪物巡逻的，这种题目本质上是在状态里再加一个时间维度，或者把怪物位置也纳入状态。但核心思想不变：把问题抽象成图上的状态搜索，用BFS逐层扩展。

1.3 状态设计与搜索空间的权衡

状态设计是这类题目的灵魂。设计得太简单，信息不够，没法正确转移；设计得太复杂，状态空间爆炸，内存和时间都扛不住。我的一般原则是：只把影响后续决策的信息放进状态里。比如钥匙拿到了就不会丢，所以需要记录；但走过的路径不需要记录，因为BFS本身保证了不会走重复的最短路。

这里有个经验性的判断方法：先列出所有可能影响“下一步能做什么”的变量，然后看这些变量的组合数量级。如果组合数在百万级别以内，BFS通常没问题；如果到了千万甚至亿级别，就得考虑双向BFS、A*启发式搜索或者别的优化手段了。

2. 核心细节解析与实操要点

2.1 地图的存储与预处理

地图一般用二维字符数组来存，常见的字符有几种：#表示墙，.表示通路，S表示起点，E表示终点，K表示钥匙，D表示门，T表示宝物。读入的时候顺手把起点位置、钥匙数量、宝物数量这些关键信息记录下来。

有个细节很多人容易忽略：地图的边界处理。我习惯在地图外围加一圈墙，这样在BFS扩展四个方向的时候就不用每次都判断是否越界，代码会简洁很多，也不容易出数组越界的bug。具体做法是把数组开大一圈，读入地图时从下标1开始存，第0行、第0列以及最后一行、最后一列全部初始化为#。

const int MAXN = 105; char maze[MAXN][MAXN]; int n, m; // 读入时外围留一圈墙 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> maze[i][j]; } }

2.2 状态的定义与去重

状态用一个结构体或者几个整数来表示。以带钥匙的迷宫为例，状态可以定义为(x, y, keyMask)，其中keyMask是一个整数的二进制位掩码，第i位为1表示已经拿到了第i把钥匙。

去重是BFS性能的关键。必须用一个visited数组来标记某个状态是否已经入过队，否则同一个状态会被反复处理，队列会无限膨胀。visited数组的维度要和状态维度一致，比如三维的visited[x][y][keyMask]。如果状态里还有宝物收集情况，那就再加一维。

注意：visited数组一定要在状态入队的时候就标记，而不是出队的时候标记。如果出队才标记，同一个状态可能在入队前被多个前驱节点重复加入队列，造成大量冗余计算。

2.3 方向数组与扩展逻辑

四个方向的扩展用方向数组来写最简洁：

int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};

每次从队列取出一个状态，尝试往四个方向走。对于每个方向，先计算新坐标，然后判断新位置是否可走。判断逻辑根据题目规则来：如果是墙，不能走；如果是门且没有对应钥匙，不能走；如果是钥匙，走过去之后要更新keyMask；如果是宝物，走过去之后要更新宝物收集状态。

这里有个容易出错的地方：更新状态之后的新状态，要用更新后的keyMask去查visited，而不是用旧的。我见过不少人在这一步写错，导致同一把钥匙被反复拿，或者拿了钥匙之后的状态没有被正确去重。

2.4 终止条件的判断

终止条件取决于题目要求。如果是“到达终点”，那就是坐标等于终点坐标时返回当前步数。如果是“收集所有宝物后到达终点”，那就需要同时判断宝物是否收集齐以及是否在终点。如果是“拿到指定钥匙”，那就判断keyMask是否包含了目标钥匙的位。

写终止条件的时候要小心：BFS第一次弹出满足终止条件的状态时，对应的步数就是最短步数，直接返回即可。不要在入队的时候就判断，因为入队时步数还没有更新到该状态的实际步数。

3. 完整实操过程与核心代码实现

3.1 题目场景设定

假设我们面对的是这样一个迷宫寻宝问题：一个n行m列的迷宫，S是起点，E是终点，.是通路，#是墙，地图上有若干把钥匙（用数字0到4表示，最多5把），对应有若干扇门（用大写字母A到E表示）。拿到钥匙后才能通过对应的门。要求从起点到终点的最短步数。

这个场景在算法竞赛中非常经典，状态压缩的技巧在这里体现得淋漓尽致。5把钥匙，状态掩码范围是0到31，状态总数最多是100×100×32=320000，BFS完全跑得动。

3.2 完整代码实现

#include <bits/stdc++.h> using namespace std; const int MAXN = 105; char maze[MAXN][MAXN]; bool visited[MAXN][MAXN][1 << 5]; int n, m; int startX, startY, endX, endY; struct State { int x, y; int keyMask; int steps; }; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int bfs() { queue<State> q; q.push({startX, startY, 0, 0}); visited[startX][startY][0] = true; while (!q.empty()) { State cur = q.front(); q.pop(); // 到达终点 if (cur.x == endX && cur.y == endY) { return cur.steps; } for (int d = 0; d < 4; d++) { int nx = cur.x + dx[d]; int ny = cur.y + dy[d]; int nMask = cur.keyMask; // 越界或撞墙 if (maze[nx][ny] == '#' || maze[nx][ny] == '\0') continue; // 遇到门，检查是否有对应钥匙 if (maze[nx][ny] >= 'A' && maze[nx][ny] <= 'E') { int doorIdx = maze[nx][ny] - 'A'; if (!(nMask & (1 << doorIdx))) continue; } // 遇到钥匙，更新掩码 if (maze[nx][ny] >= '0' && maze[nx][ny] <= '4') { int keyIdx = maze[nx][ny] - '0'; nMask |= (1 << keyIdx); } // 去重判断 if (visited[nx][ny][nMask]) continue; visited[nx][ny][nMask] = true; q.push({nx, ny, nMask, cur.steps + 1}); } } return -1; // 无法到达 } int main() { cin >> n >> m; memset(maze, '#', sizeof(maze)); memset(visited, false, sizeof(visited)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') { startX = i; startY = j; } if (maze[i][j] == 'E') { endX = i; endY = j; } } } cout << bfs() << endl; return 0; }

3.3 关键步骤的参数计算与选择依据

visited数组的大小是MAXN × MAXN × (1 << 5)，也就是105×105×32，大约35万个布尔值，占用内存约350KB，完全在竞赛题目的内存限制之内。如果钥匙数量增加到10把，状态数就变成105×105×1024，大约1100万个状态，内存占用约11MB，也还能接受。但如果钥匙数量到了20把，状态数就上亿了，这时候就得考虑别的解法。

队列里最多同时存在多少个状态？理论上界是状态总数，但实际上由于BFS逐层扩展，队列里通常只存相邻两层的状态，实际占用远小于理论上界。不过为了保险，用STL的queue就够了，它会自动扩容。

步数的更新方式是在入队时用cur.steps + 1，这样每个状态存的就是从起点到该状态的最短步数。不要在出队时累加，那样会出错。

3.4 实操中的调试记录

我第一次写这个代码的时候，犯了一个很隐蔽的错误：在判断门的时候，我写的是if (maze[nx][ny] >= 'A' && maze[nx][ny] <= 'E')，但地图里的大写字母可能不止A到E，如果题目里还有其他大写字母表示别的东西，这个判断就会误伤。后来我改成先判断是不是门，再判断是不是钥匙，最后剩下的就是普通通路，逻辑就清晰了。

还有一个坑是钥匙的编号。如果题目里钥匙用0到4表示，那maze[nx][ny] - '0'得到的就是0到4的索引。但如果钥匙用a到e表示，那就得用maze[nx][ny] - 'a'。这个细节一定要看清楚题目描述，我因为看错这个，调试了半个小时。

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

4.1 常见问题速查表

4.2 独家避坑技巧

第一个技巧是关于状态压缩的。如果钥匙数量不超过20把，可以用int的位掩码；如果到了30把以上，int就不够用了，得用long long。但一般来说竞赛题目不会出那么多钥匙，因为状态空间会爆炸。我遇到过的题目里，钥匙数量最多也就10把左右。

第二个技巧是关于双向BFS的。如果状态空间比较大，但起点和终点都明确，可以考虑从起点和终点同时做BFS，相遇时合并答案。双向BFS能把搜索空间从O(b^d)降到O(b^(d/2))，效果非常明显。不过双向BFS的实现复杂度比单向高不少，需要维护两个队列和两个visited数组，还要处理相遇时的步数合并。如果不是状态空间特别大，一般用单向BFS就够了。

第三个技巧是关于A启发式搜索的。如果题目要求最短步数，但状态空间又大到BFS跑不动，可以考虑用A，启发函数用曼哈顿距离。A*在迷宫类题目里通常能大幅减少扩展的状态数，但需要保证启发函数是可采纳的，也就是不能高估实际代价。曼哈顿距离在四方向移动的迷宫里是可采纳的，因为每次移动最多改变1的曼哈顿距离。

4.3 性能优化的几个方向

如果BFS跑得慢，可以从这几个方向优化。第一是减少状态维度，看看有没有哪些信息其实不需要放进状态里。第二是用数组代替STL队列，手写循环队列，减少内存分配的开销。第三是提前判断可行性，如果某个状态明显不可能到达终点，可以提前剪枝。第四是用位运算代替乘除法，虽然现代编译器优化已经很好了，但在竞赛环境里手动优化有时还是有用的。

还有一个容易被忽略的点是输入输出。如果地图很大，用cin和cout可能会超时，换成scanf和printf，或者加上ios::sync_with_stdio(false)和cin.tie(0)。这个优化在数据量大的时候效果很明显，我实测过，同样的代码加上这两行，运行时间能减少三分之一左右。

4.4 从迷宫寻宝延伸出去的题型

迷宫寻宝这个框架其实可以延伸到很多变体。比如多个人同时寻宝，那就是多源BFS；比如宝物有时间限制，那就是在状态里加时间维度；比如地图会动态变化，那就是在状态里加地图状态。核心思想都是一样的：把问题抽象成状态空间搜索，用BFS逐层扩展，用visited去重，用队列维护待处理状态。

掌握了这个框架之后，你会发现很多看起来复杂的搜索问题，本质上都是迷宫寻宝的变体。比如推箱子、华容道、八数码，都可以用类似的方法解决。区别只在于状态的定义和转移规则不同，BFS的骨架是不变的。

我在实际刷题的过程中，把这类题目整理成了一个模板，每次遇到新的变体，只需要修改状态定义和转移逻辑，BFS的主体代码几乎不用动。这个模板帮我节省了大量时间，也让我对BFS的理解越来越深。如果你也在准备算法竞赛，建议你也整理一个自己的模板，把常见的搜索题型都归纳进去，比赛的时候直接套用，效率会高很多。