洛谷P1825 [USACO11OPEN] Corn Maze S 这道题，算是 USACO 早期题目里非常典型的一道迷宫最短路。名字听着轻松，“玉米迷宫”，好像就是走个格子找出口的事，可只要你动手写，就会发现这里面藏着一个特别容易翻车的点：传送门。我不止一次看到周围的同学在算法题群里问这道题为什么样例过了却一直 WA，问题几乎都出在传送门的处理上。这篇文章就把这道题从建模、实现到调试讲透，代码给全，坑也给你标出来，看完你就能彻底搞懂它。
1. 先把“玉米地”翻译成图论模型
1.1 地图上的点、边、权值
迷宫题的第一步永远是把地图抽象成图。这块 N×M 的网格里，每个非墙格子就是一个节点，上下左右相邻的两个空地之间有一条无向边，走一步的代价是 1。起点 @ 是我们的源点，终点 = 是目标。于是问题就变成了“求从源点到目标点的最短路”。
这听起来平淡无奇，但 Corn Maze 的特别之处在于它引入了传送门。地图上有若干个大写字母 A 到 Z，同一个字母恰好出现两次，它们构成一对传送门。当你踩到其中一个时，会被瞬间传送到另一个相同字母所在的位置。这个“瞬间”意味着它不消耗时间。所以从图论角度来看，传送门相当于在配对的两个格子之间增加了一条权值为 0 的边。
你可能马上会想：这里有 0 权边，BFS 还适用吗？答案是适用，但不能傻乎乎地裸 BFS。因为 BFS 要求每条边的权重相同（或者说权重为 1 才能正确算出最短路）。处理的方式很巧妙：把“走一步到传送门”和“触发传送落点”合并成一个动作，整体的代价仍是 1。后面实现章节会具体展示这个打包过程。
1.2 传送门到底是“点”还是“边”
这是我建议新手先想明白的一件事。很多人的第一反应是：传送门也是一个格子，那我把它当作普通点入队，等出队时再判断要不要传送。这种思路的问题在于，一旦你把它当作普通点入队，就会把“站在传送门上”当作一种合法状态，可题目语义是“踩到传送门的瞬间就被弹走”，牛根本不会停留在这个格子上。
更合理的理解方式是：传送门不是一个可以被停留的状态，而是一个转移规则。当扩展方向带你走到某个传送门格时，你立刻从这个格子跳到另一个配对格。因此真正入队的目标点是配对传送门的位置，而不是传送门本身。这样处理既符合题意，也避免了把一个不存在的状态塞进队列。
还有一点容易忽略：传送门之间的 0 权边是双向的。你从 A 走到 A'，会被传送到另一个 A；反过来从另一个 A 走到 A'，也会被传回这里。原题这种对称设计意味着不需要特别区分方向，代码里只要找到“另一个”传送门即可。
1.3 为什么 BFS 是这道题的最优解法
先说结论：因为地图上的每条普通边权值都是 1，传送这个 0 权动作又能被打包进一步移动里，所以整张图本质上是一个无权图，无权图最短路用 BFS 是教科书级别的最优解。
为什么不选 DFS？DFS 可以找出一条从起点到终点的路径，但不保证最短。虽然加个剪枝或者回溯也能尝试枚举所有路径，但在一个 300×300 的网格里，路径数量是指数级的，完全不可行。
为什么不选 Dijkstra？Dijkstra 当然能做，但它需要优先队列，复杂度是 O(E log V)，在这个规模下完全没问题，可没必要。BFS 用普通队列，O(V+E) 线性扫完，实现还更简单，不容易写错。算法竞赛里“能用 BFS 就不用 Dijkstra”是一个很实用的选择原则。
2. 核心实现的每一步抠细
2.1 读入与预处理：起点、终点、传送门登记
这道题的读入处理直接影响后面代码的简洁程度。我的做法是：读入每一行字符串的同时，顺便完成三件登记工作。
- 遇到 @，记录起点坐标；
- 遇到 =，记录终点坐标；
- 遇到 A 到 Z，把坐标塞进对应的传送门数组。
这里有个小建议：在 C++ 里可以用vector<pair<int, int>> gate[26]来保存每种字母的传送门坐标。因为题目保证同一个字母恰好出现两次，所以读完之后每个 vector 的长度要么是 0，要么是 2。长度是 2 的时候，就用“如果当前坐标是第一个点，目标就是第二个点，否则反过来”的逻辑完成跳转。
还有一点值得注意：@ 和 = 在读入时不需要特别修改成平地。我们的 BFS 扩展逻辑并不关心当前字符是不是 @ 或 =，只要它不是墙 #，就可以走过去。唯一特殊的是判断终点，我习惯在出队时统一判断，这样扩展逻辑就不用为终点开特例。
2.2 BFS 主循环的三个关键判断
BFS 的主循环框架不复杂，但每个判断的顺序和对象都很讲究。我来拆解一下。
弹出队列头部的当前坐标后，如果它就是终点，直接返回当前步数。这里选择在出队时判断，理由是某个点一旦被入队，它的距离就已经确定，等它出队时返回一定是最优解，不会出错。
然后开始四个方向的扩展。每个新坐标要依次过三关：
- 越界检查。
nx < 0 || nx >= n || ny < 0 || ny >= m必须最先做，否则后面访问地图数组时可能越界崩溃。 - 墙检查。如果地图上是 #，直接跳过。
- 传送门检查。如果字符在大写字母范围内，需要找出配对的传送门坐标，并把原本要入队的目标坐标替换成配对点。
注意每次扩展的目标点都要用vis[tx][ty] != -1来判断是否已经访问过。这一步很多新手会漏，结果导致同一个点被反复入队，轻则队列膨胀，重则死循环。尤其有了传送门之后，你完全可能从 A 传到 A'，又从 A' 附近绕回 A，如果没有访问标记，这个环就会让你 TLE。
2.3 传送门的“跳转”实现与边界语义
跳转的实现本身不难，但有几个细节我想单独拿出来讲。
首先，jump逻辑只有在目标点是传送门时才会触发。如果某个传送门字母只出现了一次（虽然题目保证不会，但防御性编程嘛），最好直接返回原坐标，避免数组越界。这种做法不会影响正确性，但能防止你读到非预期数据时程序崩掉。
其次，传送后的目标点也可能是起点或者其它普通点，但这些情况统一交给后续的访问检查处理，不需要特殊区分。传送后的目标点如果是终点呢？一样正常入队，等它出队时返回答案，逻辑完全自洽。
最后是那个很多人纠结的问题：传送门能不能多次使用？在原题语境下，牛踩到传送门就会被传送，不存在“使用次数限制”。但我们的 BFS 通过访问标记天然保证了传送门只会被“有效”地利用一次。因为一旦某个配对目标被访问过，之后再走到任何一处传送门，跳转后都会发现目标已访问，不会再次入队。这一步免费传送不会产生更短的路，所以不需要额外记录传送门的状态。
这个处理非常优雅，说白了就是：在无权图最短路里，第一次访问就是最短距离，之后的任何访问都不可能更优，所以访问标记本身就是最强的剪枝。
3. C++ 与 Python 参考代码
3.1 C++ 满分代码
这段代码是我根据这道题的常见数据范围写的，逻辑清晰，直接提交就能过。注意dis数组同时承担了“步数记录”和“访问标记”两个职责，初始化为 -1 表示未访问。
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MAXN = 305; int n, m; char mp[MAXN][MAXN]; int dis[MAXN][MAXN]; vector<pii> gate[26]; // 传送门坐标 int sx, sy, ex, ey; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int bfs() { memset(dis, -1, sizeof(dis)); queue<pii> q; q.push({sx, sy}); dis[sx][sy] = 0; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); if (x == ex && y == ey) { return dis[x][y]; } 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; int tx = nx, ty = ny; if (mp[nx][ny] >= 'A' && mp[nx][ny] <= 'Z') { int id = mp[nx][ny] - 'A'; if (gate[id].size() == 2) { pii a = gate[id][0]; pii b = gate[id][1]; if (a.first == nx && a.second == ny) { tx = b.first; ty = b.second; } else { tx = a.first; ty = a.second; } } } if (dis[tx][ty] != -1) continue; dis[tx][ty] = dis[x][y] + 1; q.push({tx, ty}); } } return -1; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> mp[i]; for (int j = 0; j < m; j++) { char c = mp[i][j]; if (c == '@') { sx = i; sy = j; } else if (c == '=') { ex = i; ey = j; } else if (c >= 'A' && c <= 'Z') { gate[c - 'A'].push_back({i, j}); } } } cout << bfs() << endl; return 0; }为什么dis初始化为 -1 而不是 0？因为起点坐标的dis是 0，如果所有格子默认也是 0，就没法区分“访问过步数为 0 的起点”和“没访问过的格子”。用 -1 做未访问标记，0 就有明确的步数含义，代码可读性也强很多。
这里有个小坑想提醒一下：在bfs函数内部使用memset(dis, -1, sizeof(dis))没问题，因为dis是二维数组，sizeof(dis)能拿到它的完整大小。但如果你把dis换成vector<vector<int>>就不能这么写了，需要用两层循环或fill初始化。我给的这份代码直接用静态二维数组，最稳。
3.2 Python 参考实现
Python 版本同样简洁。我选择用列表存地图，用deque做队列，逻辑和 C++ 完全一致。有一点不一样：Python 字符串不可修改，所以我不去动地图，起点坐标单独记录即可。
from collections import deque n, m = map(int, input().split()) mp = [] gate = [[] for _ in range(26)] sx = sy = ex = ey = None for i in range(n): row = input().strip() mp.append(row) for j, c in enumerate(row): if c == '@': sx, sy = i, j elif c == '=': ex, ey = i, j elif 'A' <= c <= 'Z': gate[ord(c) - ord('A')].append((i, j)) def jump(x, y): idx = ord(mp[x][y]) - ord('A') if len(gate[idx]) == 2: a, b = gate[idx] return b if (x, y) == a else a return (x, y) vis = [[-1] * m for _ in range(n)] vis[sx][sy] = 0 q = deque([(sx, sy)]) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] while q: x, y = q.popleft() if (x, y) == (ex, ey): print(vis[x][y]) break for k in range(4): nx, ny = x + dx[k], y + dy[k] if nx < 0 or nx >= n or ny < 0 or ny >= m: continue if mp[nx][ny] == '#': continue tx, ty = jump(nx, ny) if vis[tx][ty] != -1: continue vis[tx][ty] = vis[x][y] + 1 q.append((tx, ty))Python 版本在跳转逻辑上跟 C++ 几乎一一对应，用jump函数单独封装传送门规则，主循环的可读性一下子就上去了。如果你在刷题的时候用 Python，这个写法比硬在循环里判断配对坐标要清晰得多，也不容易漏处理。
3.3 时间与空间复杂度分析
这道题的数据范围一般不会很大，N 和 M 通常在 300 以内，整个地图最多 9 万个格子。BFS 的时间复杂度是 O(N×M)，因为每个格子最多入队一次，每个格子向四个方向扩展，总共也就是 O(4×N×M) 的级别，很快就跑完了。
空间上，地图数组和距离数组各自是 O(N×M)，传送门数组最多只有 26 个 vector、每个最多两个坐标，可以忽略不计。总空间占用很小，不用做任何优化。
有个经验可以分享：当你写出一个 BFS 却担心超时的时候，先看状态总数是多少。有的题目状态是三维的甚至更高，那就要小心；像这道题状态就是二维坐标，而且每个状态只扩展一次，只要你的代码没有死循环，TLE 的可能性基本为零。
4. 踩坑实录与常见问题
4.1 答案比预期大 1：传送后多加了一步
这是最经典的一个错法，我当年也犯过。很多人会在dis[tx][ty] = dis[x][y] + 2，理由是“走一步到传送门 + 传送算一步”。但实际上题目里的传送是瞬间完成的，不消耗时间。走到传送门那一步已经用来产生新的坐标了，传送结束后的位置直接继承这步花费，应该只加 1。
如果你在调试时发现所有样例答案都大 1，先检查是不是这里的问题。用一个简单样例就能测试：地图只有三行三列，起点 @ 下方是 A，终点 = 在中间，A 的配对在终点右边，那么从起点到终点的最短路径就是走一步到 A，触发传送，再走一步到终点，答案应该是 2。如果你算出 3，那就是传送多算了一步。
4.2 数组越界与死循环的排查方法
数组越界的问题往往出在判断顺序上。C++ 代码里如果先访问mp[nx][ny]再判断nx是否越界，那遇到边界位置就直接访问到非法内存，轻则随机值，重则 RE。正确顺序永远是：先判越界，再判墙，最后处理传送门。
死循环则几乎是访问标记缺失导致的。有传送门的地图很容易形成环：你从 A 传到 A'，走几步又回到 A，再传一次回到 A'……如果在入队前不检查vis[tx][ty]，队列就会无限膨胀。记住 BFS 的核心防线就是“一个状态只入队一次”，这道题的状态就是坐标，所以对最终落点做去重就足够了。
4.3 传送门“使用次数”的语义坑
有些刚接触这道题的人会问一个问题：传送门用过了是不是就失效了？如果没有失效，那会不会存在反复传送的最优路径？
在原题语境下，你不需要担心这个。BFS 的访问标记已经保证了不会去反复利用传送门。原因很简单：想要利用传送门，你必须先走到传送门所在格子，这个过程本身要消耗步数。如果已经在更短步数内访问过配对目标，那再走一遍长路过来传送没有任何意义。
但如果你是拿这道题来准备更复杂的变体，比如加上了“传送门使用次数限制”，那状态设计就要改变了。这类题通常需要把状态从二维坐标扩展成“坐标 + 当前已使用的传送门集合”，复杂度会陡然升高。这个在下一节详细展开。
4.4 本地对拍与边界数据测试技巧
样例过、提交挂，几乎是算法题的常态。我建议在本地做两件事。
第一，手造几个边界数据。比如地图只有一行，起点和终点分别在两端；比如起点旁边就是终点；比如传送门的配对位置紧挨着墙。这些特殊布局能帮你确认边界条件和传送逻辑没有写错。我举一个很简单的自测样例：
3 3 @.. A=A在这个样例里，A 传送门分别出现在第二行第一列和第二行第三列，终点在它们中间。最优路径是从 @ 向下走一步到 A，触发传送到达另一边 A，再向左走一步到终点 =，总步数为 2。你可以拿这个输入去测任何实现，答案不是 2 就一定有问题。
第二，写一个朴素但对拍用的暴力程序。对拍器不需要考虑性能，可以用 DFS 穷举或者另一个思路完全不同的 BFS。生成随机小地图，把两个程序运行结果放到一起比较，只要遇到不一致，就用那组数据反推问题。这个习惯能帮你省下大量在新题上盲目试错的时间。
5. 延伸：当规则变得复杂时怎么办
5.1 传送门变形与多维状态扩展
这种“地图上有传送门”的题目，在各类竞赛里非常常见。如果把规则改成传送门只能用一次，或者只有特定数量的传送门能用，你的状态就不能只有坐标了。
举个例子：假设你最多可以使用两次传送门，每次站在传送门上可以选择“用”或“不用”。那同一个坐标在不同使用次数下就是完全不同的状态。你需要把状态设计成三元组 (x, y, used)，visited 数组也变成三维。BFS 仍然适用，但状态总数从 N×M 变成 N×M×3，转移时要同时考虑“要不要消耗一次传送机会”。这类题在思路上其实是从 Corn Maze 直接迁移过去的，理解了这道题的基础版本，变体就不难下手。
还有更花哨的变体：传送门不是成对出现而是三四个组成一个传送网络，踩到任何一个都会被随机或按规则送到另一个点。这种题本质上是多了几个分支转移，BFS 照样能做，只是转移的时候要枚举所有可能落点分别入队。
5.2 双向 BFS 与更大的地图
如果地图规模放大到 3000×3000，普通 BFS 虽然也能跑，但在某些算法竞赛的时间限制下可能会比较紧张。这时候可以试试双向 BFS：从起点和终点同时扩展，交替进行，一旦两边访问到同一个点就说明找到了最短路径的“接头点”。
但要注意，加了传送门之后，双向 BFS 的解决方案不像基础迷宫那么简单。因为传送是瞬间跳转，你在某一层扩展时可能把牛送到另一侧搜索过的区域，这时要及时判断两边是否相遇。处理得当的话，搜索空间能缩小很多，但实现复杂度也上去了。我个人的建议是：如果不确定自己能不能正确实现双向 BFS，宁可用普通 BFS，也不要在比赛中冒险写一个冗长的双向搜索，毕竟正确性永远是第一位的。
5.3 把“特殊规则”翻译成状态转移才是核心收获
刷完这道题最值得沉淀的东西，不是“我学会了一个 BFS 模板”，而是“我能把一个看似奇怪的特殊规则系统地翻译进搜索过程”。传送门并不是这道题独有的，很多题目都会在普通地图上加入瞬移、跳跃、滑行、楼梯、开关门等机制，它们的本质都是给状态转移图添加特殊边。只要你搞清楚了“当前状态 + 一个动作 = 下一个状态”这个链条，BFS 就不会迷路。
我在实际做题的时候，习惯先在草稿纸上写清楚状态定义和转移规则，再动手写代码。比如这道题，状态是 (x, y)，动作是“向上/下/左/右走一步”，但走到传送门后落点坐标会被替换，所以转移分两步：先确定移动后的坐标，再确定是否存在特殊跳转。把这两步想清楚，代码就是顺着思路打下来的，而不是边写边试。
最后再分享一个调试技巧：如果你写完后结果不对，别急着改代码，先在一个小地图上把 BFS 的访问顺序手动模拟一遍。比如上面那个 3×3 样例，手算一下每一层应该访问哪些点、距离是多少，然后给代码加上输出调试信息，对比每一层是否一致。大多数问题都能在这一步直接暴露出来。这道题值不值得刷，看你怎么用。你要是拿它练模板，十分钟就完了；你要是把传送门背后的状态设计想明白，那它带给你的收益能延伸到很多更难的迷宫题上去。
