BFS 综合训练第四课：钥匙与传送门——会思考的迷宫探险家
同学们，欢迎来到魔法王国的最后一关！
前面三课，我们已经学会了：
第一课：在地图上寻找最短路线。
第二课：不仅找到出口，还能还原最短路线。
第三课：让多个补给站一起扩散，寻找最近的补给站。
今天，迷宫要升级了！
这次，地图里有一扇被锁住的魔法门。你必须先找到钥匙，才能通过它。除此之外，地图里还有一个神奇的传送门，可以把你送到另一个位置。
这时，一个新问题出现了：
如果两个探险家站在同一个格子里，但一个有钥匙、另一个没有钥匙，他们算不算同一种情况？
不算！
这就是今天要学习的核心：BFS 不仅可以搜索位置，还可以搜索“位置 + 状态”。
一、进入魔法迷宫
我们先认识地图上的四种特殊符号。
符号 | 含义 |
|---|---|
| 探险起点 |
| 宝藏出口 |
| 钥匙，捡到后就一直拥有 |
| 锁门，只有拿到钥匙才能通过 |
| 墙壁，不能通过 |
| 普通道路 |
| 传送门 |
为了让第一次接触状态搜索的同学容易理解，我们先把问题拆成两关：
第一关：先学会“钥匙与锁门”。
第二关：再加入“传送门”。
这样一步一步来，就不会被太多规则绕晕。
二、第一关：没有钥匙，锁门就不能通过！
假设迷宫如下：
######## #S..#..# #.#D#.E# #.#....# #K.....# ########探险家从S出发，要到达E。
#是墙壁。K是钥匙。D是锁门。E是出口。
我们不能简单地把D当作普通道路，因为能不能通过它，取决于我们有没有钥匙。
如果只记录位置，会发生什么？
普通 BFS 通常会用：
visited[x][y]来表示某个格子是否访问过。
但现在想象一下：
探险家第一次到达某个格子时，还没有钥匙；后来，他绕路捡到了钥匙，又回到了这个格子。
虽然位置相同，但现在他已经可以打开锁门了！
如果程序只记住“这个格子以前访问过”，就可能把第二次到达的情况误认为没有新意义，从而漏掉可以继续探索的路线。
因此，我们需要记录两件事：
现在站在哪个格子？
有没有拿到钥匙？
这就叫作状态。
三、给探险家增加一个“钥匙状态”
我们用一个数字来记录有没有拿到钥匙：
状态 | 含义 |
|---|---|
| 还没有钥匙 |
| 已经拿到钥匙 |
于是，原来的搜索位置(x, y)，升级成：
(x,y,key)
例如：
(2,3,0)：站在第 2 行、第 3 列，还没有钥匙。
(2,3,1)：站在同一个格子，但已经拿到钥匙。
它们虽然站在同一个格子，却是两种不同的搜索状态！
怎样记录访问过没有？
原来我们使用二维数组：
visited[x][y]现在需要增加一维：
visited[x][y][key]这相当于给每个格子准备了两个小房间：
这就是今天最重要的升级：
访问过一个位置，不代表访问过这个位置的所有状态！
四、钥匙迷宫：完整编程题
我们来设计一个更适合练习的迷宫：
######### #S..#..E# #...D...# #K..#...# #########规则如下：
从
S出发，目标是到达E。每次只能向上、下、左、右移动一格。
#是墙，不能通过。走到
K就获得钥匙，之后一直拥有钥匙。
D是锁门，没有钥匙时不能进入。求从起点到出口的最少移动步数；如果到不了，输出
-1。
注意：本题的行、列从0开始计数，但这只影响程序下标，不影响我们理解地图。
第一步：队列不再只保存位置
以前的 BFS 队列保存(x,y)。
现在要保存三个数据：
queue<状态> q;为了让代码更容易理解，我们可以使用结构体：
struct Node { int x, y; int key; };这样，每个队列元素都能完整地告诉我们：
当前在哪个格子；
当前有没有钥匙。
第二步：距离也要记录状态
以前是：
dist[x][y]现在是：
dist[x][y][key]因为同一个格子在两种钥匙状态下，可能需要不同的距离，也可能有不同的后续路线。
第三步：遇到钥匙或锁门怎么办？
我们每次准备走到新格子(nx, ny)时：
如果是墙
#，跳过。如果是锁门
D，而且key == 0，跳过。如果是钥匙
K，把新状态的key设为1。如果这个新状态已经访问过，不再重复加入队列。
否则记录距离并入队。
注意：捡到钥匙后，状态就从0变成1，之后不会变回0。
五、C++ 完整参考程序
#include <iostream> #include <queue> #include <string> using namespace std; const int N = 105; struct Node { int x, y; int key; }; int n, m; char mp[N][N]; // dist[x][y][0]：没有钥匙时到达该格子的最短距离 // dist[x][y][1]：有钥匙时到达该格子的最短距离 int dist[N][N][2]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int main() { cin >> n >> m; int sx = -1, sy = -1; int ex = -1, ey = -1; // 1. 读入地图，初始化距离 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mp[i][j]; dist[i][j][0] = -1; dist[i][j][1] = -1; if (mp[i][j] == 'S') { sx = i; sy = j; } if (mp[i][j] == 'E') { ex = i; ey = j; } } } // 2. 起点入队，开始时没有钥匙 queue<Node> q; Node start; start.x = sx; start.y = sy; start.key = 0; q.push(start); dist[sx][sy][0] = 0; // 3. BFS 搜索 while (!q.empty()) { Node cur = q.front(); q.pop(); int x = cur.x; int y = cur.y; int key = cur.key; // 到达出口，当前状态的距离就是答案 if (x == ex && y == ey) { cout << dist[x][y][key] << "\n"; return 0; } // 尝试向上下左右移动 for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; // 不能走出地图 if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; } // 不能穿墙 if (mp[nx][ny] == '#') { continue; } // 没有钥匙，不能进入锁门 if (mp[nx][ny] == 'D' && key == 0) { continue; } // 计算走过去后的钥匙状态 int nkey = key; if (mp[nx][ny] == 'K') { nkey = 1; } // 这个位置和钥匙状态已经访问过 if (dist[nx][ny][nkey] != -1) { continue; } // 记录新状态的距离 dist[nx][ny][nkey] = dist[x][y][key] + 1; // 新状态入队 Node nxt; nxt.x = nx; nxt.y = ny; nxt.key = nkey; q.push(nxt); } } // 队列空了还没找到出口 cout << -1 << "\n"; return 0; }输入
5 9 ######### #S..#..E# #...D...# #K..#...# #########输出
10这里最短路线需要先向下绕到钥匙所在位置，再返回中间通道，通过锁门，最后抵达出口。BFS 会自动比较所有可行路线，找到步数最少的路线。
六、第二关：加入神奇的传送门！
钥匙已经学会了，现在我们给迷宫增加一种新机关：传送门。
新规则是：
地图中有两个
P。当探险家走进其中一个
P，就会立刻传送到另一个P。传送过程不额外消耗步数：从相邻格子走进传送门，算移动一步，落到另一个传送门后可以继续行动。
钥匙仍然有效，拿到后不会丢失。
我们要想一想：加入传送门后，BFS 的核心思想需要改变吗？
答案是：不需要！仍然是一层一层搜索，只是每次移动时，要按照传送门规则确定真正到达的位置。
1. 先找到两个传送门
读入地图时，记录两个传送门的坐标：
int px1 = -1, py1 = -1; int px2 = -1, py2 = -1;如果遇到第一个P，记录它的位置；遇到第二个P，记录另一个位置。
2. 走进传送门后，改变目的地
假设我们计算出准备走到(nx, ny)。
如果它是普通格子，目的地就是(nx, ny)。
但如果它是传送门，就要把目的地改成另一个传送门的位置。
int tx = nx; int ty = ny; if (mp[nx][ny] == 'P') { if (nx == px1 && ny == py1) { tx = px2; ty = py2; } else { tx = px1; ty = py1; } }接下来，不是访问原来的(nx, ny)，而是访问传送后的(tx, ty)。
别忘了：检查访问记录、更新距离、加入队列，都应该针对传送后的目的地进行。
3. 钥匙和传送门一起使用时，记录什么？
仍然是：
(x,y,key)
其中：
x：当前行；y：当前列；key：有没有拿到钥匙。
传送门只改变位置，不会让钥匙消失。因此传送后的新状态是：
(tx,ty,key)
这就是状态搜索最有趣的地方：移动规则可以很特别，但只要我们能够明确下一步到达哪里，就仍然可以用 BFS 搜索最短路。
七、把今天的思路整理成一张表
普通迷宫 | 钥匙迷宫 | 钥匙与传送门迷宫 |
|---|---|---|
记录位置 | 记录位置和钥匙状态 | 记录位置和钥匙状态 |
上下左右移动 | 上下左右移动，锁门需要钥匙 | 上下左右移动，锁门需要钥匙，传送门改变目的地 |
|
|
|
传送门不会额外增加一种钥匙状态，所以我们不需要再加一个portal维度。我们只要根据规则算出下一步的真正目的地即可。
八、课堂小测验
第 1 题：为什么钥匙迷宫不能只使用visited[x][y]？
A. 因为地图中可能有很多行
B. 同一格子在有钥匙和没有钥匙时，是不同状态
C. 因为队列不能保存坐标
答案：B。
同一位置的不同钥匙状态必须分别记录。
第 2 题：探险家拿到钥匙后，又通过了传送门，钥匙状态会怎样？
A. 自动丢失钥匙
B. 变回没有钥匙
C. 仍然拥有钥匙
答案：C。
传送门只改变位置，不会让钥匙消失。
第 3 题：加入传送门后，BFS 的核心思想是什么？
A. 仍然按最短距离一层一层搜索
B. 不需要队列了
C. 只要走进传送门就立刻找到出口
答案：A。
BFS 仍然按照距离层次搜索，只是移动规则发生了变化。
九、今天的BFS 状态搜索口诀
普通迷宫，记录位置。
遇到钥匙，再记状态。
相同位置，状态不同，不能混为一谈。
遇到传送门，先算真正目的地。
队列分层搜索，找到最短路线。
本课最值得孩子们掌握的，不是把代码背下来，而是学会一种新的思考方法：
解决问题时，先想清楚：为了决定下一步怎么走，我究竟需要记录哪些信息？
有时候，位置就够了；有时候，还需要记录钥匙、能量、剩余次数等状态。只要把状态设计正确，BFS 就能帮助我们解决越来越复杂的最短路问题。
