小学四年级也能看懂的BFS（10、BFS 综合训练第四课：钥匙与传送门——会思考的迷宫探险家）

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..#…#
#########

规则如下：

注意：本题的行、列从 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 就能帮助我们解决越来越复杂的最短路问题。