如果你准备过华为OD机试应该对“双机位C卷”这几个字不陌生。同一套题里双机位意味着考试过程有前后两个摄像头全程录像C卷则代表这套试卷使用了C卷题库。而Alice的安全旅行是C卷里一道非常有区分度的搜索题它表面上是地图寻路实际却隐藏了“状态”这个关键考点。这篇文章我就以这道题为例把题目还原、算法推导、五种语言的实现差异和机试现场可能踩的坑一次性讲透适合正在刷华为OD机试的同学也适合想真正搞懂状态BFS的人。1.1 双机位C卷到底在考什么心态先聊几句机试环境。华为OD的机考一般是三道题总分400分左右两道一星题加一道二星题Alice的安全旅行通常出现在二星题的位置。双机位的意思是电脑摄像头拍正面手机或者第二摄像头放侧后方拍屏幕全程防作弊监控。这种环境最真实的压力是你不能借助任何外部工具只能靠平时练出来的手感和思路。很多人平时刷题靠搜索题解、靠IDE自动补全、靠编译报错改错上了双机位考场才发现思路一旦卡住心态很容易崩。所以我会在最后专门说机试现场的节奏控制。先说题目本身。1.2 Alice的安全旅行常见题目描述是什么样的这道题在网络上有多个版本我按最常出现、也最有训练价值的版本整理如下Alice要从地图左上角出发到达右下角。地图是一个N行M列的二维网格每个格子是0或者10表示安全1表示危险。Alice每一步只能向上、下、左、右四个相邻格子移动要求整条路径上经过的危险格子数量不超过K。请问Alice能否到达终点如果能输出最少需要走多少步如果不能输出-1。有的版本会把“危险格子数量”改成“危险值之和”格子值变成不同数字这种情况下题目会从BFS升级成带权最短路我后面会单独说。但绝大部分C卷复现题里用的是0/1网格加K限制。1.3 输入输出格式常见的输入格式是第一行三个整数 N M K 接下来 N 行每行 M 个整数0或1比如4 4 2 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0输出一个整数表示从(0,0)到(3,3)的最少步数如果非法则输出-1。如果你在机试里遇到的输入格式不同比如K写在最后一行或者地图用字符串给出改一下读取逻辑即可核心算法不变。1.4 这题为什么容易被看走眼很多人的第一反应是“这不就是个BFS求最短路吗遇到1就绕开”。问题就在这里。普通BFS只能处理“某条路不能走”这种硬性限制而Alice的限制是“你可以走危险格但总共最多走K个危险格”。这完全是两种规则。举个例子一条路径20步经过2个危险格另一条路径5步有3个危险格。如果K2那么20步那条是合法路径5步那条反而是非法路径。最短路径不一定合法合法路径不一定最短。不理解这一层后面做多少都没用。2.1 一个反例同样步数危险消耗不同我们再看细一点。假设当前有两条路径都能走到地图中间某个格子P路径A走到P用了5步累计经过了2个危险格路径B走到P也用了5步累计经过了0个危险格。如果只用一个普通二维数组visited来记录“P点是否被访问过”一旦A先到达Pvisited[P]被标记为trueB后到P时就会被直接拦住。但B明显比A更优因为B消耗的危险配额更少后续从P出发能走的范围更广。这就是裸BFS在这个题里会翻车的根本原因。再换个角度如果A先到把P占住了而终点就在P旁边但被危险格包围B本来可以轻松走出去却因为visited被A占掉而失败。这不是算法细节问题是建模就错了。2.2 状态BFS把“剩余危险配额”纳入状态正确的做法是把“当前累计经过了多少危险格”也当作搜索状态的一部分。状态可以写成三元组(x, y, danger)表示“走到格子(x,y)时共经过了danger个危险格”。如果当前danger已经大于K这个状态就非法。理论上这个状态空间是三维的访问标记也可以是三维数组visited[x][y][danger]。搜索从(0,0, grid[0][0])开始每走一步到新格子(nx,ny)如果grid[nx][ny] 1新的状态变成(nx, ny, danger1)如果grid[nx][ny] 0新的状态变成(nx, ny, danger)。当到达(N-1,M-1)时第一次出队的步数就是最短步数因为BFS天然按层扩展。三维visited保证了同样一个格子、同样一种危险消耗水平不会被重复入队。比如我们走了3步到达(2,2)累计2个危险记作visited[2][2][2]后来5步到达(2,2)也累计2个危险但步数更长这种情况可以直接剪掉因为后面的拓展只会更差不会更优。2.3 压缩到二维最佳值数组效率更高三维数组在N、M很大的时候会浪费内存实际上我们可以用一个二维数组best[i][j]来记录“到达(i,j)时最少累计危险值”核心判断逻辑是如果当前danger小于best[nx][ny]就更新best[nx][ny]并尝试入队如果当前danger大于等于best[nx][ny]说明之前已经有更优路径到达过这个格子当前状态不可能产生更好结果剪掉。为什么只保留最小danger就够因为BFS有个重要特性第一次扩展到某个状态时步数一定不是更差的那一档。假设两条路径都到达同一个格子步数相同危险值更小的那条显然更优应该保留步数更大但危险值更小的路径要不要保留看上去危险值小是优势但步数已经大了在BFS中它会占一个更高的层而由于我们已经记录了该格更小危险的到达状态未来从该格出发时使用的是最佳状态步数更大的那条不会产生更短答案所以可以剪掉。这个压缩技巧非常关键它让状态从三维降到二维同时保证正确性。这也是机试高手和普通刷题者的一个明显分水岭。2.4 记忆化DFS也是一种等价写法如果不喜欢BFS也可以用DFS加记忆化。递归函数dfs(x, y, danger, steps)继续往下搜遇到边界就剪枝用best[x][y]记录到当前格子的最小危险值如果当前dangerK或者已经大于等于best则返回。但DFS在找最短路径时通常要搜完整棵搜索树性能不如BFS稳定机试时我不推荐作为首选。如果一开始想到的是DFS可以快速验证小数据再改成BFS提交。3.1 C/C结构体队列手写队头队尾C和C在机试里的优势是速度快大数据量也不慌。队列可以用STL的queue也可以手写数组模拟队列。手写队列在需要频繁访问队头队尾时更直观而且不用管理动态内存。核心结构体这么设计struct Node { int x, y; // 坐标 int danger; // 走到当前格时累计危险值 };BFS主循环伪代码int bfs(vectorvectorint grid, int K) { int n grid.size(), m grid[0].size(); const int INF 1e9; vectorvectorint best(n, vectorint(m, INF)); queueNode q; if (grid[0][0] K) return -1; best[0][0] grid[0][0]; q.push({0, 0, grid[0][0]}); int dirs[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int steps 0; while (!q.empty()) { int sz q.size(); while (sz--) { auto cur q.front(); q.pop(); if (cur.x n-1 cur.y m-1) return steps; for (auto d : dirs) { int nx cur.x d[0], ny cur.y d[1]; if (nx 0 || ny 0 || nx n || ny m) continue; int nd cur.danger grid[nx][ny]; if (nd K || nd best[nx][ny]) continue; best[nx][ny] nd; q.push({nx, ny, nd}); } } steps; } return -1; }注意这里用BFS的分层遍历确保每个steps对应一步。在C提交时vector的初始化比较快但如果地图特别大也可以用原生数组减少初始化开销。3.2 Pythondeque和元组拆包要熟练Python写BFS最舒服的就是collections.deque。队列元素可以用元组(x, y, danger)但元组拆包在极端大的地图上会比列表慢一点点。机试时优先保证逻辑清晰。from collections import deque def min_steps(grid, N, M, K): if grid[0][0] K: return -1 INF 10**9 best [[INF] * M for _ in range(N)] best[0][0] grid[0][0] q deque() q.append((0, 0, grid[0][0])) dirs [(-1,0),(1,0),(0,-1),(0,1)] steps 0 while q: for _ in range(len(q)): x, y, d q.popleft() if x N-1 and y M-1: return steps for dx, dy in dirs: nx, ny x dx, y dy if 0 nx N and 0 ny M: nd d grid[nx][ny] if nd K and nd best[nx][ny]: best[nx][ny] nd q.append((nx, ny, nd)) steps 1 return -1这段代码有个很实用的点通过len(q)做分层就不需要在节点里额外记录步数逻辑更干净。Python的缺点是当N、M到1000以上时入队频繁会慢但OD机试的数据范围通常不会让Python跑不过去除非你写了很多低效操作。3.3 Java类对象入队 vs 数组降维Java写这道题最简单是定义一个静态内部类static class Node { int x, y, danger; Node(int x, int y, int danger) { this.x x; this.y y; this.danger danger; } }用ArrayDeque 当队列。ArrayDeque在大量入队出队时比LinkedList更稳定推荐使用。但Java的类对象会创建大量小对象队列深的时候对GC压力很大。省内存的写法是把三维坐标压缩成一维因为地图大小最多N*M用idx x * m y然后在数组里分别存x、y、danger反而更麻烦。实际上我更推荐直接用int[3]入队或者把danger单独开一个二维数组存。Queueint[] q new ArrayDeque(); q.offer(new int[]{0, 0, grid[0][0]});这是性能和代码复杂度之间的平衡。Java机试时还要注意输入用BufferedReader而不是Scanner因为Scanner在大量数据读取时可能超时。3.4 JavaScript队列用普通数组加索引指针JavaScript刷这道题最容易踩的坑是用shift()当出队操作。shift()的时间复杂度是O(n)每次出队都会移动后面所有元素数据一多直接超时。正确做法是用数组配合头指针function minSteps(grid, N, M, K) { if (grid[0][0] K) return -1; const INF 1e9; const best Array.from({ length: N }, () Array(M).fill(INF)); best[0][0] grid[0][0]; const queue [[0, 0, grid[0][0]]]; let head 0; const dirs [[-1,0],[1,0],[0,-1],[0,1]]; let steps 0; while (head queue.length) { let size queue.length - head; while (size--) { const [x, y, d] queue[head]; if (x N - 1 y M - 1) return steps; for (const [dx, dy] of dirs) { const nx x dx, ny y dy; if (nx 0 nx N ny 0 ny M) { const nd d grid[nx][ny]; if (nd K nd best[nx][ny]) { best[nx][ny] nd; queue.push([nx, ny, nd]); } } } } steps; } return -1; }这个head指针的方式相当于手写队列出队不删除元素只移动索引时间复杂度O(1)。JavaScript的数组动态扩容有一定损耗但比shift()好几个数量级。3.5 Go结构体切片队列Go在机试里的清爽程度仅次于Python。定义结构体、用切片当队列即可。type Node struct { x, y, danger int } func minSteps(grid [][]int, N, M, K int) int { if grid[0][0] K { return -1 } const INF 1e9 best : make([][]int, N) for i : range best { best[i] make([]int, M) for j : range best[i] { best[i][j] INF } } best[0][0] grid[0][0] queue : []Node{{0, 0, grid[0][0]}} dirs : [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} steps : 0 for len(queue) 0 { size : len(queue) for i : 0; i size; i { cur : queue[i] if cur.x N-1 cur.y M-1 { return steps } for _, d : range dirs { nx, ny : cur.xd[0], cur.yd[1] if nx 0 nx N ny 0 ny M { nd : cur.danger grid[nx][ny] if nd K nd best[nx][ny] { best[nx][ny] nd queue append(queue, Node{nx, ny, nd}) } } } } queue queue[size:] steps } return -1 }这里有个细节每层处理完用queue queue[size:]把已出队的元素丢弃。这个操作会重新切片底层数组还在但头指针移动了内存占用是可控的。如果在循环里不断append底层数组会自动扩容性能也不错。4.1 起点和终点的危险值到底算不算这是这道题最大的版本分歧。我查过多个复现题不同博主给的题解对起点的处理都不一样。我建议的做法是起点必须判断终点也必须判断。起点如果本身就是危险格且K grid[0][0]说明第一步就超出了配额直接返回-1。终点同理。但更稳妥的办法是在写代码之前先看题目给的示例。机试时题目不会模糊到让你猜考试界面会有明确的示例输入输出。如果示例里起点是1且K是0但答案不是-1那说明起点危险不消耗配额这时候你需要把初值设为best[0][0]0入队时danger也传0。我个人习惯统一按“消费配额”处理因为这样逻辑更自洽也不容易在边界上漏掉。如果题目描述不一致改一行初始化就行。4.2 K特别大的时候三维状态反而会爆炸如果K很大比如N*M那么大理论上危险配额不再是约束问题退化成普通BFS。此时如果你用三维visited[x][y][danger]去标记会因为danger维度过大而严重浪费内存。用二维best数组就完全没有这个顾虑因为best只存最小dangerK再大也只是数值大小问题。所以二维best数组方案不仅在效率上优在空间上也是天然安全的。4.3 N1或M1的退化地图很多人刷题习惯了N和M都大于1忽略了单行或单列的情况。当地图是一行时BFS的dirs数组里上下方向的移动都会越界这没问题但你要确认终点(0, M-1)是否可达。比如N1, M5, K1地图是[0,1,0,1,0]Alice必须经过两个1但K1答案应该是-1。这种退化数据是机试自测时的重点用例一定要单独测。4.4 读入时最容易出的问题Java用Scanner读大数据量容易超时建议用BufferedReader按行读再split空格。C用cin外面加std::ios::sync_with_stdio(false)否则大数据量输入会拖慢。Python用sys.stdin.readline不要用input()尤其是地图行数很多的时候。Go的fmt.Scan足够应付一般数据量但如果地图特别大可以用bufio.Scanner。很多考生不是算法错了而是输入超时导致提交失败非常可惜。4.5 变体危险值变成权重后就不是BFS了如果题目里每个格子不是0/1而是不同的危险等级比如0到9的整数要求路径上危险总和不超过K那用BFS层数来计数就不对了因为不同格子的消耗不同步数和消耗是一对多关系。这种情况标准解法是Dijkstra边权视作走到相邻格子的额外危险值dist数组维护的是“最小累计危险值”而不是步数。如果你还想同时保证步数最小可以把状态扩展成(step, danger)在dist[danger]里记录最小步数或者用Dijkstra时优先级按步数排其次才考虑危险值。这个扩展我建议练一下因为机试变体题经常把一种算法包装成另一种。5.1 考场上的第一选择用最熟的语言写正确再谈优化机试时间有限千万不要在考场上尝试“用不熟的语言挑战自己”。你应该选出你最熟练的语言先把题目AC如果还有余力再用第二语言尝试。这题用Java、C、Python都不难但前提是你对语言的BFS模板足够熟能三分钟内无错误地写出来。如果你平时用Python刷题考试却要求你用Java那就应该在考前先把Java的BFS模板、输入输出模板各写十遍。模板是肌肉记忆不是临场思考题。5.2 自测用例清单写完代码后至少要自测这几组最简单的地图1行1列输出0。这时起点就是终点不应该走任何一步。无需经过危险格即可到达。必须经过危险格但配额足够。危险格数量刚好超过K输出-1。终点的危险值超出K导致不可达。大N、大M的地图验证不会超时。第1组最容易被人忽略。很多人BFS初始化就把steps设为0然后入队起点队头弹出时如果位置是终点返回0这没问题。但如果你把起点入队前判断成“经过起点算一步”返回1就错了。5.3 3分钟思路检查法我给自己定过一个小规矩拿到一道搜索题先用三分钟把三件事想清楚再动键盘状态是什么(x, y, danger)状态转移是什么走一步时danger加不加什么条件下终止任一条路径到达终点输出当前步数想不清楚这三件事写代码就是碰运气。状态想清楚了代码只是翻译。5.4 常用输入输出模板参考这里给一个Python的完整读入模板已经被我讲过很多次适合所有二维网格类题目import sys from collections import deque def main(): data sys.stdin.read().strip().split() if not data: return it iter(data) N int(next(it)) M int(next(it)) K int(next(it)) grid [] for _ in range(N): row [int(next(it)) for _ in range(M)] grid.append(row) print(min_steps(grid, N, M, K)) if __name__ __main__: main()用sys.stdin.read一次性把全部输入读进来再split是Python机试最快也最不容易写错的读法。C可以用getline分行走Java用BufferedReader基本同理。我在实际准备时见过太多人把大量时间花在和编译器搏斗、和输入格式搏斗、和“为什么本地跑得挺对一提交就错”搏斗上。Alice这道题真正有价值的不是背一个BFS模板而是理解“危险配额”如何成为状态的一部分。把这个想明白后面遇到带资源约束的寻路题比如燃油限制、时间限制、携带物品数量限制你都能秒懂出题人想考什么。希望这篇拆解能帮你少走点弯路。
