洛谷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 是教科书级别的最优解。为什么不选 DFSDFS 可以找出一条从起点到终点的路径但不保证最短。虽然加个剪枝或者回溯也能尝试枚举所有路径但在一个 300×300 的网格里路径数量是指数级的完全不可行。为什么不选 DijkstraDijkstra 当然能做但它需要优先队列复杂度是 O(E log V)在这个规模下完全没问题可没必要。BFS 用普通队列O(VE) 线性扫完实现还更简单不容易写错。算法竞赛里“能用 BFS 就不用 Dijkstra”是一个很实用的选择原则。2. 核心实现的每一步抠细2.1 读入与预处理起点、终点、传送门登记这道题的读入处理直接影响后面代码的简洁程度。我的做法是读入每一行字符串的同时顺便完成三件登记工作。遇到 记录起点坐标遇到 记录终点坐标遇到 A 到 Z把坐标塞进对应的传送门数组。这里有个小建议在 C 里可以用vectorpairint, 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 pairint, int pii; const int MAXN 305; int n, m; char mp[MAXN][MAXN]; int dis[MAXN][MAXN]; vectorpii 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)); queuepii 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换成vectorvectorint就不能这么写了需要用两层循环或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 .. AA在这个样例里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 样例手算一下每一层应该访问哪些点、距离是多少然后给代码加上输出调试信息对比每一层是否一致。大多数问题都能在这一步直接暴露出来。这道题值不值得刷看你怎么用。你要是拿它练模板十分钟就完了你要是把传送门背后的状态设计想明白那它带给你的收益能延伸到很多更难的迷宫题上去。