BFS与传送门：USACO玉米迷宫最短路问题全解析

最近在整理USACO早期题单的时候，又刷到了洛谷P1825这道 Corn Maze，突然想专门聊聊它。题目本身评级不算高，属于 Silver 组别，但信息量一点都不小：普通迷宫的 BFS 最短路大家都会写，一旦加上“传送门”这种机制，很多人的代码就开始各种翻车。我见过太多人卡在同一个地方，不是 BFS 不会写，而是“传送门到底该怎么处理”没想明白。

这道题讲的是：一头牛在玉米地里找出口，地里除了普通空地、玉米墙，还有成对出现的传送门。牛每走一格算一步，一旦踩上传送门，会被瞬间送到另一个相同字母的传送门位置，然后继续走。目标是找到从起点到出口的最短步数。很适合拿来练 BFS，也很适合用来理解“状态设计”这件事。不管你是刚开始刷 USACO，还是准备打基础，这道题都值得认真写一遍。

1. 先把题意啃透：玉米迷宫到底长什么样

1.1 地图上的字符，每一个都代表什么

这道题的地图是一个 N×M 的网格，字符含义非常明确，做题第一步不是急着写代码，而是先把这些字符归类清楚。我习惯先列一张表：

这里最容易被忽略的是：传送门格子本身不是墙。很多新手在看题的时候，会把传送门当成一种“特殊事件格”，下意识觉得它不是空地，甚至有人会把它当成障碍物直接跳过，这是完全错误的。传送门可以踏入，踏入后会被传送，传送本身不额外消耗步数，这一点非常关键。

还有一个小细节，每个字母的传送门在地图中恰好出现两次。也就是说，地图上如果有两个A，它们互为传送关系；如果有两个B，它们也互为传送关系。不会出现某个字母只出现一次的情况，这算是 USACO 给的一个保证，也降低了预处理的复杂度。

1.2 “传送”到底怎么计步，是这道题的第一道坎

我第一次写这道题的时候，心里就在犯嘀咕：从普通格子走进传送门，再被弹到远处，这一下到底算一步还是算两步？题目原意是：牛正常走一格，就消耗一个单位时间；走进传送门的那一刻，传送是瞬间完成的，不再额外耗时。所以从某个格子移动到传送门所在格子，总步数只加 1，传送后的位置仍然停留在同一层。

理解了这一点，你会发现传送门本质上就是给两个相距很远的格子之间加了一条“不花步数的快速通道”。这也意味着，BFS 在进行四个方向的扩展时，如果发现目标格子是传送门，就应该立刻把它替换成配对的另一个传送门坐标，然后这个替换后的坐标才是真正要入队的点。

很多错误代码都是在这里多加了一次步数，导致样例能过、大数据就 WA。判断标准很简单：你在做dist[nx][ny] = dist[x][y] + 1的时候，不管中间是否经历了传送，这个+1就是移动的那一步，传送本身不能再加任何东西。

1.3 从“迷宫最短路”到“带传送门的图模型”

如果把整张地图看成一个图，每个格子是一个节点，能互相走到的相邻格子之间存在一条边，那么这道题就是在求从起点节点到出口节点的最短路径。传送门相当于在配对的两个节点之间连了一条“特殊边”，而且这条边的代价同样是 1 步。

这样抽象之后，问题就变得非常干净：普通迷宫的最短路可以用 BFS，加了传送门之后，只要在扩展时把传送门的特殊边处理好，BFS 依然适用。图论里这个思想叫“隐式建图”，我们不需要真正把图结构存下来，只需要在遍历到某个格子时，知道它的邻居有哪些、特殊转移有哪些，就足够了。

2. 为什么这道题非 BFS 不可

2.1 BFS 天然保证最短路的原理

BFS 的全称是广度优先搜索，它按“层”来遍历图。起点是第一层，起点一步能到的所有点是第二层，两步能到的点是第三层，以此类推。因为每一层都比上一层多一步，所以第一次访问到目标节点的层数，就是起点到该节点的最短步数。

这个性质依赖两个条件：第一，每一步的代价相同，都是 1；第二，图是无权图，或者所有边权相同。这道题完全满足。所以当你第一次从队列里弹出出口节点时，dist[ex][ey]里存的就是答案，可以立刻输出。

有个很形象的类比：往水里扔一颗石子，波纹一圈一圈向外扩散。先到达某个位置的波纹，一定是走的最短路径；后面到达的波纹只会更远。BFS 就是模拟这个过程。

2.2 用 DFS 搜最短路会踩什么坑

DFS 适合做连通性判断、回溯搜索、拓扑排序这类问题，但它在找最短路上有天然的劣势。DFS 会沿着一条路一头扎到底，直到撞墙才回头。虽然可以通过反复更新最小值来找到答案，但最坏情况下需要尝试所有路径，在网格图上这不是指数级就是极其低效。

有人说我可以加剪枝，步数超过当前最优就回溯。这在理论上是可行的，但面对 300×300 的地图，一旦加入传送门，路径数量会变得非常可观，剪枝也很难救回来。更关键的是，DFS 不是按层扩展的，它第一次到达出口时，根本不知道这条路是不是最短的，必须完整搜索所有可能性才能确认。与其硬写 DFS，不如一开始就用 BFS。

2.3 BFS 代码骨架，先温习一遍再说

BFS 的经典骨架在迷宫题里几乎是固定的。我每次写都会下意识过一遍：

• 需要一个队列，存待扩展的坐标。
• 需要一个距离数组，初始化为 -1，表示没有访问过。
• 起点入队，距离设为 0。
• 每次从队首弹出节点，先判断是不是终点。
• 如果不是终点，就朝四个方向扩展，能走的节点距离加 1 并入队。

这套骨架里最容易写错的就是方向数组和距离更新。方向数组建议固定为上下左右：{-1,0}, {1,0}, {0,-1}, {0,1}。距离更新一定是在入队之前完成，而且要检查越界、墙、是否访问过这三个条件，顺序可以是越界、墙、访问、传送门处理。

3. 传送门处理：全题最容易被坑的地方

3.1 先用预处理把传送门配对存好

写代码前先把传送门的映射关系准备好。最简单的做法是开一个长度为 26 的vector，每个元素存坐标对。读地图时，遇到字母就把坐标塞进对应的桶里。等整张图读完之后，每一个桶里都有两个坐标，它们就是互相配对的传送门。

这样在后面 BFS 的过程中，只需要根据当前格子的字母，找到这个桶里不等于当前坐标的那一个，就是它的传送目标。这个过程是 O(1) 的，不会成为性能瓶颈。

有一种更省事的写法是用一个数组记录每个字母第一个出现的位置，第二个出现时直接建立双向映射。但我个人更喜欢vector存储，因为逻辑清晰，查错也方便，两个坐标一目了然。

3.2 我的推荐写法：移动入队前就完成传送

传送门的处理时机有两种思路：一种是“出队时处理”，也就是从队列里弹出坐标后，先判断当前点是不是传送门，如果是就先跳到配对点，再做四方向扩展；另一种是“入队前处理”，也就是在扩展方向时，发现下一个格子是传送门，就立刻把坐标替换成配对坐标，再走常规的判断和入队流程。

我推荐第二种。原因是它更贴合题意的语义：牛是“走到传送门格子”才触发传送，传送完成后的落点才是它真正站的位置。代码写起来也更不容易出隐蔽错误。伪代码大概是这样的：

nx = x + dx[k] ny = y + dy[k] 如果越界，跳过 如果 mp[nx][ny]是墙，跳过 如果 mp[nx][ny]是传送门： 把 (nx, ny) 替换成配对的传送门坐标 如果 (nx, ny) 已经访问过，跳过 距离 = 当前距离 + 1 入队

这样写的好处是，传送门的配对坐标在入队时就已经是“最终落点”，后续不需要再判断它是不是传送门。这里可能会有人疑惑：传送门配对坐标本身也是同一个字母，它不是传送门吗？从字符上看确实是，但它作为落点时，牛已经完成了这次传送，不应该再次触发。如果写成“出队时处理”，反而很容易绕进“传送过去又传回来”的死循环里。

3.3 访问标记到底标在哪里

这道题访问标记的设计非常容易出错。我刚开始写的时候，把访问标记加在了传送门入口上，结果出现了一些很别扭的问题。后来想明白了一个原则：dist数组记录的是牛“实际站立的格子”的最短步数，而不是“触发过传送的格子”的最短步数。

按照我推荐的“入队前传送”写法，真正入队的是传送后的落点。所以只需要在传送后，给落点标记访问即可。传送门入口被踩中只是瞬间事件，牛并不会在那里停留，因此不需要给入口标记dist。

那会不会造成重复计算？比如有四条路都能走到传送门入口，那么这四条路都会尝试把配对出口入队。但因为出口已经被第一个到达的路径标记过了，后面三次尝试都会被剪枝。也就是说，多余的只是三次 O(1) 的坐标替换和访问判断，不会导致队列膨胀，也不会影响正确答案。

如果你想更严格地剪枝，也可以单独开一个vis数组，把入口和出口都标记成已访问。但我个人建议初学阶段先理解“只标记实际落点”的做法，因为它是纯正的距离语义，不容易和其他逻辑混淆。

3.4 边界、墙和传送门，判断顺序怎么排

地图问题里，扩展方向时的判断顺序很影响代码简洁度。我推荐的顺序是：越界判断最先做，因为数组下标非法会导致运行时错误；然后判断墙；接着判断传送门；最后判断是否访问过。

墙和传送门不会同时存在，所以先判断墙再判断传送门没有隐患。唯一要注意的是，不要把传送门判断放在访问标记的后面。原因是：如果先检查dist[nx][ny] != -1就跳过，那么当nx, ny是传送门入口且曾经被某种方式触发时，就可能错过一次也许能通向更短路径的传送。虽然大多数时候不会出问题，但逻辑上不够严谨。

4. 完整可提交代码：C++ 与 Python 对照

4.1 C++ 版

C++ 在竞赛里永远是主力，读入快、运行快、调试方便。下面这版代码我直接在洛谷这类平台提交过，整体结构清晰，适合作为模板：

#include <bits/stdc++.h> using namespace std; const int MAXN = 305; int n, m; char mp[MAXN][MAXN]; int dist[MAXN][MAXN]; int sx, sy, ex, ey; vector<pair<int, int>> portal[26]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; pair<int, int> getPair(int x, int y) { int id = mp[x][y] - 'A'; for (auto p : portal[id]) { if (p.first != x || p.second != y) { return p; } } return {x, y}; // 正常情况下不会到这里，因为每个字母恰好出现两次 } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mp[i][j]; if (mp[i][j] == '@') { sx = i; sy = j; } else if (mp[i][j] == '=') { ex = i; ey = j; } else if (mp[i][j] >= 'A' && mp[i][j] <= 'Z') { portal[mp[i][j] - 'A'].push_back({i, j}); } } } memset(dist, -1, sizeof(dist)); queue<pair<int, int>> q; q.push({sx, sy}); dist[sx][sy] = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == ex && y == ey) { cout << dist[x][y] << '\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] >= 'A' && mp[nx][ny] <= 'Z') { auto p = getPair(nx, ny); nx = p.first; ny = p.second; } if (dist[nx][ny] != -1) { continue; } dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } cout << -1 << '\n'; return 0; }

这段代码的核心就两个点。第一，getPair通过字母索引找到配对坐标，只返回与当前坐标不同的那一个。第二，传送门的坐标替换发生在扩展阶段，而不是入队后再次处理。

4.2 Python 版

Python 写这种题最大的优势是逻辑直观，适合在本地验证想法。缺点是常数略大，但在 N、M 最大 300 的情况下完全够用。下面是 Python 代码：

from collections import deque n, m = map(int, input().split()) mp = [] portal = [[] for _ in range(26)] sx = sy = ex = ey = -1 for i in range(n): row = list(input().strip()) mp.append(row) for j, ch in enumerate(row): if ch == '@': sx, sy = i, j elif ch == '=': ex, ey = i, j elif 'A' <= ch <= 'Z': portal[ord(ch) - ord('A')].append((i, j)) def get_pair(x, y): idx = ord(mp[x][y]) - ord('A') for p in portal[idx]: if p != (x, y): return p return (x, y) dist = [[-1] * m for _ in range(n)] dq = deque([(sx, sy)]) dist[sx][sy] = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while dq: x, y = dq.popleft() if (x, y) == (ex, ey): print(dist[x][y]) break for k in range(4): nx, ny = x + dx[k], y + dy[k] if not (0 <= nx < n and 0 <= ny < m): continue if mp[nx][ny] == '#': continue if 'A' <= mp[nx][ny] <= 'Z': nx, ny = get_pair(nx, ny) if dist[nx][ny] != -1: continue dist[nx][ny] = dist[x][y] + 1 dq.append((nx, ny)) else: print(-1)

Python 这里有个很容易踩的坑：读入时如果用input()后直接拼接字符串，要注意每行末尾可能带有换行符，strip()一定要加。另外，portal里的坐标是元组，判断p != (x, y)的时候没有问题，但如果你把坐标存成列表就需要注意类型一致。

4.3 一份手算样例带你走一遍

光看代码不如手动跑一遍。我构造一个简单的用例：

3 4 @.A. .... ..A=

地图中起点是(0,0)，出口是(2,3)，两个A分别位于(0,2)和(2,2)。

如果不走传送门，从起点到出口的曼哈顿距离是 5，图为空地，所以最短路是 5 步。但地图里有传送门，正确路径应该是：从(0,0)走到(0,1)，再走到(0,2)，步数记为 2；踩上A后瞬间传送到(2,2)，步数仍然是 2；最后向右一步到达(2,3)，总步数 3。

用 BFS 跑一遍：起点dist[0][0]=0；扩展四个方向，dist[0][1]=1；继续扩展，走到A时直接替换为(2,2)，所以dist[2][2]=2；最后从(2,2)扩展到(2,3)，dist[2][3]=3，输出 3。这个例子也直观说明了传送门给最短路带来的优化。

4.4 洛谷提交时的输入输出细节

这道题的读入是按字符读的，没有空格，所以用cin读字符非常方便。但要注意，如果用scanf读字符串，要小心换行符残留。cin >> mp[i][j]会自动跳过空白字符，问题不大。

输出就一个整数，最短步数。题目保证有解，但如果你用我上面的代码，万无一失的写法还是加一个找不到出口输出-1的保护分支，以免某些魔鬼数据故意卡你。

另外，竞赛平台对 C++ 提交时建议加上ios::sync_with_stdio(false); cin.tie(0);，否则输入输出同步的开销在极限数据下也可能造成区别。Python 提交则尽量用sys.stdin.read()代替多次input()，但 N、M 只有 300 时无所谓，习惯好一点而已。

5. 常见错误与 Debug 实录

5.1 我见过的 WA/RE 原因清单

这道题的提交记录里，最常见的错误其实非常集中。我把它们整理成一张速查表，方便大家自查：

这里面最严重的是死循环。如果你把传送逻辑写成“只要当前点是传送门就不断跳转”，在配对的两个传送门之间就会无限跳跃。我的解决方法就是前面强调的：传送只在移动进入传送门的瞬间处理一次，配对后的落点不再循环判断。

5.2 用 dist 矩阵打印做可视化排查

Debug BFS 最简单粗暴也最有效的方法，就是把dist数组直接打印出来。整个 BFS 跑完之后，你可以看到每一个格子的最短距离，然后人工沿着数字 0、1、2、3… 走一遍，立刻能看出问题出在哪。

比如你发现传送门的出口格子上dist突然比预期少了 1，说明可能在传送时少加了步数；如果发现传送门出口没有被更新，说明传送门处理根本没被执行。对网格题来说，视觉化排查往往比盯着代码发呆快得多。

我曾经在调试这道题时，把整个地图的dist打印了三次才定位到问题：我写getPair的时候，返回了当前坐标自身，结果传送后根本没动。这种低级错误，靠肉眼盯着代码很难发现，打印出来一眼就能看到：传送门两端的距离完全一样，说明传送没有发生。

5.3 一次真实的传送门死循环排查

有一次我帮一个同学看代码，他用的策略是“出队后先判断当前点是不是传送门，是就跳转”。结果程序在本地跑一个样例时直接卡死。原因很有意思：他把传送门配对坐标入队后，下一次出队又会触发传送，于是两个传送门之间反复横跳，队列越积越多。

解决方案也很简单。要么在传送后给入口和出口都打上访问标记，要么改成“入队前处理”的思路。我最后帮他改成了入队前处理，因为这样不需要额外维护“哪些传送门已经用过”的状态，逻辑更自然。

从这次经历中我总结出一个原则：传送门这类“状态改变”的处理，最好放在“从一个节点走向另一个节点”的过程中，而不是放在“从队列中取出节点之后”。前者是单次事件，后者容易引入不必要的重复触发。

5.4 提交前的自测 checklist

我写这种带特殊机制的 BFS 题，提交前会快速过一遍下面的检查清单：

• 传送门是否在输入阶段就完成了配对存储。
• 传送后是否修改了坐标再去做访问判断。
• 传送过程有没有额外增加步数。
• 队列里是否只存坐标，不存多余的步数信息。
• 起点和出口坐标是否被正确记录。
• 数组大小是否比 N 和 M 的最大值再大一点。
• 四个方向数组是否和坐标习惯一致。

这些检查花不了十秒钟，但能避免大量无意义的提交记录。尤其是数组大小，N 和 M 上限是 300，我习惯直接开到 305，多留一点余量。

6. 这道题刷完，还能往哪些方向延伸

6.1 复杂度分析：为什么 300×300 随便跑

BFS 的复杂度是 O(V + E)，V 是节点数，也就是 N×M 个格子；E 是边数，每个格子最多向四个方向扩展，所以边的数量也是 O(N×M)。传送门处理是常数时间，不会改变复杂度。因此整道题的复杂度是 O(N×M)，空间复杂度同样是 O(N×M)，主要开销在dist数组和队列。

N 和 M 都是 300 时，总节点数只有 9 万，BFS 瞬间就能跑完。所以这道题完全不担心性能，真正需要担心的是逻辑正确性。

6.2 传送门题的变种与进阶

刷完这道题之后，可以试着想想下面这些变种，每一个都会逼你把 BFS 理解得更深：

• 传送门不止两个，变成多个点互相连接。
• 传送门有使用次数限制，用完就失效。
• 进入传送门需要消耗额外的时间。
• 需要输出完整路径，而不是只输出最短步数。
• 传送门出口可能被墙挡住，处理时要额外判断。
• 地图更大，需要 A* 或者 Dijkstra 才能高效解决。

这些变种里，传送门有使用次数限制的情况特别有意思，因为它涉及到“状态”的维度：你不仅要记录当前在哪个格子，还要记录哪些传送门已经被用过。这就是从普通 BFS 升级到状态 BFS 的典型例子。

6.3 从“坐标 BFS”到“状态 BFS”的思维跃迁

很多人在刷完这道题之后，觉得只是学会了一种传送门的处理方式。但在我看来，这道题更大的价值是帮你建立“状态”的概念。

普通的 BFS，状态就是坐标(x, y)。而一旦题目中加入钥匙、传送门剩余次数、时间限制等条件，状态就变成了(x, y, keyMask, portalUsed...)。此时只需要把队列元素从二元组扩展成多元组，距离数组也从二维扩展成多维，BFS 的框架依然成立。

Corn Maze 中的传送门，就是“坐标到坐标”的状态转移。理解了这一点，后面再遇到类似问题时，你会很自然地思考：这个场景里还需要记录哪些信息？这些信息有没有可能让状态爆炸？如果不会爆炸，BFS 就是首选。

最后分享一个小技巧。写这类带特殊机制的搜索题，我习惯在代码开头就把所有规则用注释写一遍，比如“走入传送门立即传送，且传送不消耗额外步数”。不要小看这一步，它能防止你写着写着就忘了题目的语义。我在这道题上踩过最大的坑，就是自以为理解了题意，结果代码里多加了一次传送步数。如果你现在去写这道题，我建议你也先花两分钟把“传送门触发一次，落点不重复触发”这句话写下来，再动手敲代码。