华为OD机考陷阱方格题：BFS最短路径与五语言实现详解

做过在线机考的人应该都有这种感觉算法题本身往往不难真正要命的反而是那些“题目看懂了但不知道从哪下手”搜索题。华为OD机考双机位C卷里经常出现一道非常典型的“陷阱方格/机器人走迷宫问题”地图上有起点、终点、空地还有一种不可通行的陷阱格子。表面看它只是道搜索题实际考察的是BFS最短路径的底层理解以及ACM模式下不同语言的基本功。这篇我就把这个题完整拆开题目什么样、为什么一定选BFS不选DFS、Java/Python/JS/C/Go五种语言各怎么实现、双机位考场上有哪些容易丢分的细节最后再聊聊它的变体能怎么迁移。准备机考或者刷题冲刺的人把这篇当成模板复盘效率会高很多。1. 陷阱方格的题目原貌描述、样例与输入输出的坑1.1 我整理后的标准题目描述这道题在题库里的叫法有两个有的套卷写“陷阱方格”有的写“机器人走迷宫”但核心设定是一致的。在一个 M 行 N 列的方格地图上S是机器人起点E是终点.是可以通行的空地#是陷阱。机器人每一步可以向上、下、左、右四个方向移动一格移动到空地、起点或终点都耗时 1 分钟陷阱格子不能进入。要求计算从S到E的最短耗时如果机器人根本到不了终点输出-1。输入格式是典型的在线评测风格第一行两个整数 M 和 N由空格隔开。接下来 M 行每行一个长度为 N 的字符串表示一行地图。题目保证地图里至少存在一个起点和一个终点。输出就一个整数最短耗时不可达则输出-1。这类题的数据范围在不同套卷里略有区别常见的是M, N 500或者M, N 1000。单看数据量不算大但如果你用错算法500x500 的规模照样可能把程序跑爆。1.2 一个手工分层计算的样例先给一个我经常拿来演示的样例3 4 S... .#.# ...E地图里S在 (0,0)E在 (2,3)。#分别在 (1,1) 和 (1,3)是两块不可通行的陷阱。BFS 的扩展过程可以按“层”来看第 0 层队列里只有 (0,0)步数为 0。第 1 层从起点向四个方向扩展得到 (0,1) 和 (1,0)。第 2 层继续扩展最远到达 (0,2) 和 (2,0)。第 3 层扩展出 (0,3) 和 (2,1)。第 4 层扩到 (1,3) 和 (2,2)。第 5 层从 (1,3) 或 (2,2) 到达 (2,3)也就是终点E。所以我手工算出的答案是5。你可以在本地跑一下你写的任何语言版本这个样例的输出必须是5否则代码里肯定有细节问题。1.3 输入输出环节的边界坑这类题的读入细节非常容易炸而且炸得毫无征兆。我自己的经验是读每一行地图字符串之前一定要去掉首尾空白。在线评测系统的输入行末尾经常带\r这样的回车符你不处理grid[i][j]访问到最后一个有效字符之后就全乱了。Python 里用strip()Java 里用trim()JS 里用trim()C 的cin 会跳过空白所以问题不大Go 的fmt.Fscan同理但如果你用bufio.Scanner自己Scan也要记得调Text()之后自己清理。另一个坑是输入读取方式。Java 我习惯用Scanner读两个整数然后用sc.next()逐行读地图字符串而不是nextLine()和nextInt()混用。因为nextInt()之后按一次回车缓冲区里会残留换行符这时直接调nextLine()很容易读到一个空字符串。很多人第一次写这个题就栽在这里。防御性处理也要有如果读完整张地图发现S或E不存在直接输出-1返回。虽然题目说保证存在但多写两行防御逻辑总比在某些奇怪输入上直接数组越界崩掉要好。2. 为什么先想到BFS图论模型、复杂度与DFS的对比2.1 把方格地图还原成无权图模型看到迷宫先别急着写代码脑子里的第一件事是把地图抽象成图。每个方格是一个节点相邻并且都可以走的两个格子之间连一条无向边。因为每走一步耗时 1所以所有边的权重都是 1这是一张不折不扣的无权图。“从起点到终点的最短耗时”本质就是“无权图上两个节点之间的最短路径长度”。这个建模能力就是机考要考的核心之一。一旦把问题归约成无权图最短路径算法选择其实已经锁死了BFS。不是因为它听起来最“搜索”而是因为从起点出发BFS 天然按距离从小到大逐层扫描节点。2.2 同样叫搜索DFS为什么在这道题不行很多人拿到迷宫题第一反应是 DFS 回溯。DFS 能判断“能不能到”但你问它“最短要几步”它就得把所有从起点到终点的路径都试完才能拍胸脯说哪个最短。在 500x500 的地图里即使路径本身不太多理论上最坏情况的状态数量也是指数级爆炸的。有人会说DFS 加 visited 剪枝之后每个格子只走一次不也很快吗这里有个关键误区DFS 加 visited 之后它找到的是“某一条可行路径”不是最短路径。如果你在 DFS 过程中发现某个格子已经被访问过就回头第一次到达终点时走过的路径可能绕了远路。要得到最短路径必须允许“通过不同路径再次到达同一个格子”那回溯规模又会爆炸。这是 DFS 在最短路径问题上最尴尬的地方。BFS 之所以适合是因为队列先进先出的特性正好把节点按“距离起点多少层”排好了顺序。第一层是距离 1 的节点第二层是距离 2 的节点依次类推。第一次从队列里弹出终点时当前记录的距离一定是全局最短。这个分层性质是 BFS 和最短路径之间的天然桥梁。2.3 复杂度是多少visited 数组为什么那么重要设格子总数 V M × N。在方格地图里每个格子最多向四个方向扩展所以边的总数 E 不超过 4V。BFS 的时间复杂度就是 O(V E)化简之后是 O(V)空间复杂度 O(V)。当 MN1000 时V 是 10^6哪怕邻居判断做四百万次Java、C、Go 都是毫秒级完成Python 用优化过的输入和deque也能在一秒上下跑完。这也是为什么这道题根本不需要上 Dijkstra 或者 A*无权图上 BFS 已经是最优工具。visited 数组的作用是让每个格子最多入队一次。这里有个细节标记的时机一定要选对入队的时候立刻标记而不是出队的时候才标记。如果拖到出队才标记同一个格子可能在队列里被加入很多次最坏情况下队列会膨胀数倍时间和空间都会被拖垮。这个细节在数据量小时看不出来M 和 N 到几百以上时差距非常明显。3. 五种语言的完整实现Java/Python/JS/C/Go逐行过一遍3.1 Java 版Main 类、Scanner 与 Queue在线评测对 Java 的第一要求是类名必须是Main并且有public static void main(String[] args)。我用Scanner读两个整数再用sc.next()读每一行地图字符串。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); char[][] grid new char[m][n]; int si -1, sj -1, ei -1, ej -1; for (int i 0; i m; i) { String line sc.next(); for (int j 0; j n; j) { grid[i][j] line.charAt(j); if (grid[i][j] S) { si i; sj j; } else if (grid[i][j] E) { ei i; ej j; } } } int[][] dirs { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; boolean[][] visited new boolean[m][n]; Queueint[] queue new LinkedList(); queue.offer(new int[] {si, sj, 0}); visited[si][sj] true; while (!queue.isEmpty()) { int[] cur queue.poll(); int x cur[0], y cur[1], step cur[2]; if (x ei y ej) { System.out.println(step); return; } for (int[] d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] ! #) { visited[nx][ny] true; queue.offer(new int[] {nx, ny, step 1}); } } } System.out.println(-1); } }这段代码里队列元素用的是int[]数组一次存 x、y、step 三个值。这么做写起来快、读起来清楚在线评测完全够用。如果你很在意性能也可以自定义一个Node类但这道题的数据规模下int[]不会成为瓶颈。3.2 Python 版deque 与 sys.stdin.readlinePython 是很多人的首选因为写起来最短。但 Python 的性能余量最小输入一定要用sys.stdin.readline不要用裸的input()。当输入行数一多input()在底层缓冲上的开销会明显拖慢速度。import sys from collections import deque def solve(): input sys.stdin.readline m, n map(int, input().split()) grid [] si sj ei ej -1 for i in range(m): row input().strip() grid.append(row) for j, ch in enumerate(row): if ch S: si, sj i, j elif ch E: ei, ej i, j visited [[False] * n for _ in range(m)] visited[si][sj] True q deque() q.append((si, sj, 0)) dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: x, y, step q.popleft() if x ei and y ej: print(step) return for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and not visited[nx][ny] and grid[nx][ny] ! #: visited[nx][ny] True q.append((nx, ny, step 1)) print(-1) if __name__ __main__: solve()两点提醒。第一deque.popleft()是 O(1) 的千万别用list.pop(0)后者每次都要把整个列表前移一位数据一多就是灾难。第二地图我保留了字符串而不是转成字符二维表Python 字符串可以直接用grid[nx][ny]访问字符少一层list嵌套内存和时间都更友好。3.3 JavaScript 版readline 事件模型与队列指针JS 版最特别的地方是输入方式。Node.js 环境里没有浏览器的prompt必须用readline逐行读入而且代码写在事件回调里。整体结构是先攒输入所有行读完之后在close事件里执行 BFS。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let m -1, n -1; let grid []; let si -1, sj -1, ei -1, ej -1; let lineCount 0; rl.on(line, (line) { line line.trim(); if (m -1) { const parts line.split(/\s/).map(Number); m parts[0]; n parts[1]; } else { grid.push(line.split()); for (let j 0; j n; j) { if (grid[lineCount][j] S) { si lineCount; sj j; } else if (grid[lineCount][j] E) { ei lineCount; ej j; } } lineCount; } }); rl.on(close, () { const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]]; const visited Array.from({ length: m }, () Array(n).fill(false)); const queue [[si, sj, 0]]; visited[si][sj] true; let head 0; while (head queue.length) { const [x, y, step] queue[head]; if (x ei y ej) { console.log(step); return; } for (const [dx, dy] of dirs) { const nx x dx; const ny y dy; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] ! #) { visited[nx][ny] true; queue.push([nx, ny, step 1]); } } } console.log(-1); });JS 最容易踩的坑是队列实现。新手看到队列第一反应是queue.shift()但shift()会把整个数组头部移除并让所有元素前移复杂度 O(n)。数据一大这个看似无害的调用会让整道题超时。我这里用head指针模拟队头只让head递增数组本身只做push整体代价接近 O(1)是最适合在线评测的写法。3.4 C 版queue 与方向数组C 的代码最接近“教科书”适合追求性能和稳定的人。两个必须做的优化一是关闭 iostream 与 C stdio 的同步二是结构体队列代替tuple可读性好且访问快。#include bits/stdc.h using namespace std; struct Node { int x, y, step; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin m n; vectorstring grid(m); int si -1, sj -1, ei -1, ej -1; for (int i 0; i m; i) { cin grid[i]; for (int j 0; j n; j) { if (grid[i][j] S) { si i; sj j; } else if (grid[i][j] E) { ei i; ej j; } } } vectorvectorbool visited(m, vectorbool(n, false)); queueNode q; q.push({si, sj, 0}); visited[si][sj] true; int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x ei cur.y ej) { cout cur.step \n; return 0; } for (int i 0; i 4; i) { int nx cur.x dirs[i][0]; int ny cur.y dirs[i][1]; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] ! #) { visited[nx][ny] true; q.push({nx, ny, cur.step 1}); } } } cout -1 \n; return 0; }#include bits/stdc.h在很多在线评测环境是可用的如果你担心编译环境严格可以换成iostream、vector、queue、string四个具体头文件。另外注意vectorvectorbool在 C 标准里有特殊的位压缩实现性能没问题但别对内部 proxy 行为做太多假设。3.5 Go 版切片队列的 head 索引Go 的代码风格和其他语言不太一样切片虽然可以当队列用但如果用queue queue[1:]弹出队头底层数组前面那些已经出队的元素迟迟不会被回收数据量大时会白白占着内存。更干净的写法还是用一个head索引指向逻辑队头。package main import ( bufio fmt os ) type Node struct { x, y, step int } func main() { reader : bufio.NewReader(os.Stdin) var m, n int fmt.Fscan(reader, m, n) grid : make([]string, m) si, sj, ei, ej : -1, -1, -1, -1 for i : 0; i m; i { fmt.Fscan(reader, grid[i]) for j : 0; j n; j { switch grid[i][j] { case S: si, sj i, j case E: ei, ej i, j } } } if si -1 || ei -1 { fmt.Println(-1) return } visited : make([][]bool, m) for i : range visited { visited[i] make([]bool, n) } dirs : [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} queue : make([]Node, 0, m*n) queue append(queue, Node{si, sj, 0}) visited[si][sj] true head : 0 for head len(queue) { cur : queue[head] head if cur.x ei cur.y ej { fmt.Println(cur.step) return } for _, d : range dirs { nx, ny : cur.xd[0], cur.yd[1] if nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] ! # { visited[nx][ny] true queue append(queue, Node{nx, ny, cur.step 1}) } } } fmt.Println(-1) }Go 的二维切片初始化要写两层内层忘记make的话访问visited[i][j]会直接 panic。另一个小点是fmt.Fscan读取字符串时会自动跳过空白所以你不需要像 JS 那样手动 trim。整体上 Go 的语法开销很小又是编译型语言在线评测里性能表现非常稳。3.6 五种语言实现对照一览语言输入读取队列实现方向数组写法visited 类型JavaScanner.nextQueueint[] LinkedListint[][]boolean[][]Pythonsys.stdin.readlinedeque.popleft常量列表二维 list 布尔值JavaScriptreadline close数组 head 指针数组嵌套二维数组布尔值Ccin queueNodeint dirs[4][2]vectorvectorboolGofmt.Fscan bufio.Reader切片 head 索引[4][2]int二维 bool 切片这张表不用背考前把自己要用的那一行看熟就够。核心差异其实就是两件事怎么读入标准输入以及用什么结构当队列。理解了这个换任何语言都不会慌。4. 双机位C卷考场实战提交细节、性能防御与边界case4.1 双机位下的环境准备与考试节奏在线机考采用双机位监控已经是很常见的安排了一个摄像头拍考生正面另一个拍侧后方或桌面区域。这种环境下代码写得熟不熟是一回事考场的物理布置和操作习惯是另一回事。我自己的习惯是提前一晚就把桌面清空只留电脑、键盘、鼠标、证件和必要文具。手机放在另外一个房间或者在监考要求下放在指定区域。浏览器通知、聊天软件弹窗、同步盘弹窗全部提前关掉不然考试中途突然弹出一条消息既打扰思路还容易引发不必要的误会。开考前按照系统指引测试两个摄像头确认画面能完整覆盖要求区域再进入正式考试界面。这些问题看着琐碎但任何一个出了状况都比多写一道算法题更影响结果。4.2 ACM模式提交的关键约定类名、入口、标准输出机考的提交方式和 LeetCode 这类平台不太一样它要求的是一个完整可运行的程序不是只写一个类方法。Java 的类名必须是Main方法签名必须是public static void main(String[] args)。Go 必须有package main和func main()。Python 直接从标准输入读、往标准输出写就行但注意不要再写任何交互提示比如请输入M和N之类的print那都会当成答案的一部分直接 Wrong Answer。输出内容只能是结果本身结尾要不要换行其实不严格但多输出一个空格、一个逗号、一句调试日志基本就告别这道题了。我见过有同学调试的时候忘了删print提交后一直全错还以为是 BFS 写挂了最后才发现是日志输出混进了答案。所以提交前一定检查输出分支只留那一行真正的答案。4.3 性能防御输入优化和可选的小技巧数据范围到 1000x1000 时Python 版本的性能余量会明显低于其他语言所以 Python 选手更要注意输入写法。用sys.stdin.readline代替input()是第一优先。其次地图行保留字符串而不转字符二维表能省掉一部分内存。如果数据量继续加大还可以把(x, y)坐标压缩成一维整数idx x * n y放进队列出队时再x idx / n, y idx % n还原。这样每个队列元素从三元组变成单个整数队列内存和 GC 压力都会小不少。Java 选手如果遇到超时第一件要检查的事是输入读取。Scanner在单条数据只有几个数字时没问题但整体输入量上去之后会比BufferedReader慢不少。把Scanner换成BufferedReader加StringTokenizer或者直接用split往往立竿见影。C 选手则要记得ios::sync_with_stdio(false); cin.tie(nullptr);这行不加大数据量下 iostream 可能慢到接近超时边界。4.4 三个亲测容易翻车的细节第一个方向数组写错。四条方向我几乎固定写成{{-1,0},{1,0},{0,-1},{0,1}}分别对应上、下、左、右。如果你习惯写成顺时针{{0,1},{1,0},{0,-1},{-1,0}}只要别手滑把加减号搞反就行。这类低级错误不是思考深度的问题纯粹是手速太快所以方向数组越简单越固定越好。第二个起点忘记标记 visited。这个错误很隐蔽因为程序还能跑甚至小数据也能出正确结果——起点在下一层扩展时又被加入队列形成一次无效遍历。但如果地图里存在从起点出发绕一圈又回到起点的路径严格来说队列里会有起点副本数据量一大就会产生冗余扩展。标准做法就是入队时立刻visited[si][sj] true不要有任何侥幸。第三个终点判断时机搞混。判断终点可以在入队时做也可以在出队时做。我习惯在出队时判断取到当前节点后先看它是不是终点是就直接输出当前step。这个写法的逻辑是“每个节点弹出时都代表最短步数的第一次访问”和 BFS 分层性质完全对齐不太会出现步数差一的问题。如果你选择在入队时判断对应输出应该是step 1注意别把步数漏加。还有一个稳赚不赔的小习惯拿到地图后先检查si和ei是否仍然是-1是就直接-1输出。虽然题目保证至少有一个起点和一个终点但多写两行防御逻辑能省掉很多不可控的输入异常。5. 从陷阱方格出发加权迷宫、传送门等变体迁移5.1 变体一陷阱可以走但扣能量答案要用什么如果把题目改成#不是不能走而是踩一次要扣掉 N 点能量要求找一条“累计扣分最少”的路径BFS 就不够了。因为每条边的代价不再是统一的 1而是根据进入的格子不同有不同权重BFS 的分层性质会失效。这时候正确工具是 Dijkstra用优先队列按“当前累计消耗”从小到大出队dist[x][y]记录到达每个格子的最小消耗弹出一个节点时如果它已经是终点输出对应的累计消耗即可。Python 里最简洁的实现是用heapqimport heapq hq [(0, si, sj)] # (累计消耗, x, y) dist [[float(inf)] * n for _ in range(m)] dist[si][sj] 0 while hq: cost, x, y heapq.heappop(hq) if cost dist[x][y]: continue if x ei and y ej: print(cost) return for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] ! #: add 陷阱扣分 if grid[nx][ny] # else 0 if cost add dist[nx][ny]: dist[nx][ny] cost add heapq.heappush(hq, (cost add, nx, ny))如果你遇到的是“扣分只分 0 和 1 两档”的特殊版本更优的思路是 0-1 BFS0 代价的边插到队首1 代价的边插到队尾。这样既保持 BFS 的线性复杂度又能处理双档权重。5.2 变体二传送门、转向限制、多终点的处理框架传送门是这类迷宫题最喜欢的变体。地图上会出现若干对传送门某个格子可能是传送入口踩上去就瞬间移动到另一个对应格子。处理方式并不复杂在 BFS 扩展邻居时额外判一次当前位置是不是传送门是的话就把传送目标点也当作一个邻居入队。如果传送也消耗步数就把step 1传进去如果传送不消耗就直接step完全不改变 BFS 框架。转向限制则是另一个维度。比如机器人只能直行或右转不能掉头、不能左转。这时候单纯的“格子是否访问过”不够了因为你到达同一个格子时的朝向不同后续能走的方向也不同。visited 状态要从“格子”升级成“(格子, 朝向)”。队列里每个元素除了 x、y、step还要保存当前朝向。这个升级理解起来有点绕但本质就是“状态 BFS”在更大的状态空间里做和原来完全相同的事。多终点也好办。地图上有好几个出口要求到任意一个都行。最稳妥的写法是 BFS 从起点出发第一次弹出的任意终点就是最短答案。如果题目反过来要从多个出口同时向一个目标扩散多源 BFS 也很好用先把所有出口作为一个批次塞进队列谁先碰到目标谁就是最近出口。5.3 一套模板能吃下多少题从迷宫到状态空间把“方格迷宫”抽象成“节点 邻居生成 visited 判定”三个组成部分你会发现 BFS 能套进非常多的题目里。打开转盘锁是典型的状态 BFS。四位密码锁的每一位就是一个状态位每个状态向后拨一位产生 8 个邻居这里面“死锁”列表就相当于陷阱不能用。单词接龙是另一种状态图单词之间只有一个字符不同才会连边BFS 求的是最少转换次数。还有腐烂的橘子本质是多源 BFS把所有初始腐烂的橘子同时入队扩散的层数就是全部腐烂需要的时间。岛屿数量更像是连通性检测从每个没访问过的陆地格子开始 BFS把所有连成片的陆地标记完启动了几次 BFS就有几座岛。这套模板的价值就在这里你真正要练的不是背五个语言的代码而是拿到任何题都能快速识别出“节点、邻居、visited”这三件事分别是什么。陷阱方格只是这三件事最直白的一种呈现方式。我备考那阵子把这道题在每个语言里各写了一遍最后发现真正拉开差距的永远是读入有没有坑、队列实现有没有性能隐患、边界 case 有没有判全。如果你现在还在为“背了模板还是不会套”发愁我的建议很直接用你考试要用的语言把这道陷阱方格完整跑通从 stdin 输入地图、到 stdout 输出结果一遍不吃鸡就换变体再练。能把一道题吃透到这种程度上机遇到它的那一刻它就不是难题而是送分题。