企业官网建设流程全解析

前阵子有朋友回传一道某大厂OD机考C卷的真题，题名是「周末爬山」，要求用 Java 写。我一开始以为题目里会有一堆山路、索道、体力值的设定，结果读下来发现内核特别经典：在二维矩阵上做可达性搜索，顺便记录最短步数。双机位考试模式下，现场不能切窗口查资料，代码熟练度直接决定能不能一次 AC。这篇文章就把这道题从读题、选算法、写代码到机考实操的完整链路拆一遍，给准备 OD 机考、尤其是刚开始刷网格搜索题的人做个参考。读完你不仅能照着写出可运行的 Java 解法，还能搞明白哪些细节容易丢分、为什么同一套代码换一个输入就报错。

1. 题目到底在考什么：先把“周末爬山”读明白

1.1 一份比较典型的C卷题干

我按常见的 C 卷版本还原一下题面：给定一个 n 行 m 列的地图 grid，grid[i][j] 表示这个位置的海拔高度；再给一个整数 k，表示一次移动允许的最大高度差。你从左上角 (0,0) 出发，每次可以向上、下、左、右移动一格，移动条件是目标格子的海拔与当前位置的海拔差绝对值不超过 k。现在要输出两个数：能到达的最高海拔是多少；如果存在多个格子都是这个最高海拔，到达其中任意一个位置所需的最少步数是多少。

注意这里的关键词是“能到达”和“最少步数”。不是整个地图里最高的那个数，而是从左上角出发、按照 k 的限制能真正走到的最高点。如果你被一片高墙拦住，那高墙后面的山峰再高也和你没关系。很多人第一反应是找全图最大值，然后直接算曼哈顿距离，那就掉进陷阱了。题目考的是在有约束的网格上做搜索，不是纯粹的几何计算。

这个版本的时间限制通常比较宽松，矩阵规模一般不超过几百乘几百。但也别因此轻视它，越是基础题，越容易出现“样例过了但隐藏用例挂掉”的情况，后面我会专门列容易踩的坑。

1.2 为什么首选 BFS 而不是 DFS

看到“最短步数”四个字，第一选择应该是 BFS（广度优先搜索）。原因不复杂：在无权网格里，每次移动的代价都是 1，BFS 按层扩展，第一次扩展到某个格子时，记录下来的步数就是起点到该格子的最短步数。你不需要反复比较多条路径，队列天然保证逐层推进。

DFS 能做吗？能做。但如果用递归 DFS 去找最短步数，你得把所有可行路径都搜完，最后才能比较出最短的那条。地图一旦大起来，递归深度可能直接把栈打爆，运行时间也完全不可控。就算你用迭代栈加 visited，也很难保证第一次访问到目标时就是最短路径。所以 DFS 更适合“只问可达性”的题目，一旦题目要求最短路，BFS 是更稳的方案。

还有个容易被忽略的点：这道题的状态很简单，只有“当前坐标”这一维，没有额外的钥匙、血量、剩余步数等状态。这意味着可以用一个二维 visited 数组去重，不需要引入复杂的状态压缩。如果以后遇到带额外状态的网格题，那就得考虑用更高维的 visited，但这不是今天这道题的重点。

1.3 从样例推演一遍，建立手感

光看文字不好理解，我拿一个具体输入走一遍。

假设输入是：

3 3 1 0 1 2 3 2 1 0 0 1

起点是 (0,0)，海拔 0，k=1。起点能走到哪些格子？上下左右只需要看右边 (0,1) 海拔 1，差值是 1，不超过 k，可以走；左边没有格子；下边 (1,0) 海拔 3，差值是 3，超过 k，不能走；上面没有格子。于是第一层只有 (0,1)。

到了 (0,1) 海拔 1，再往下扩展，右边 (0,2) 海拔 2，可走；下边 (1,1) 海拔 2，可走；左边起点已经访问过，跳过。所以第二层有两个格子 (0,2) 和 (1,1)，步数都是 2。

继续扩展，从 (1,1) 可以走到下边 (2,1) 海拔 1，差 1，可走；左边 (1,0) 海拔 3，差 1，可走；右边 (1,2) 海拔 1，差 1，可走。第三层会出现 (1,0) 海拔 3，步数 3。

到这一步，当前遇到的最高海拔已经是 3，而且步数是 3。之后即使还有别的路径能走到 (1,0)，步数也不可能比 3 更短，因为 BFS 已经按层走到了这里。所以最终输出是3 3。

这个推演过程能帮你直观理解 BFS 的“层序感”。写代码前，拿个小样例在纸上画一画，很多边界问题都会提前暴露。

2. 核心细节：状态设计、访问标记与高度差判断

2.1 队列里到底放什么信息

BFS 队列里每个元素至少需要三个信息：x 坐标、y 坐标、当前步数。Java 里有两种常见写法，一种是新建一个内部类：

static class Node { int x, y, step; Node(int x, int y, int step) { this.x = x; this.y = y; this.step = step; } }

另一种是直接用int[]数组，比如new int[]{x, y, step}。两种都能跑，考试时我建议用数组，写起来最短，也省得定义类。但要注意Queue<int[]>的可读性确实差一些，如果你更习惯类的方式，用内部类完全没问题。

这里有个性能常识：ArrayDeque比LinkedList更适合当队列。LinkedList虽然也实现了 Queue 接口，但它的节点创建和删除开销更大；ArrayDeque是循环数组实现，在 BFS 这种频繁入队出队的场景下更稳。代码里直接写Queue<int[]> queue = new ArrayDeque<>();就好。

2.2 visited 数组为什么必须在入队时标记

这是 BFS 最常见的一个坑：标记访问的时机不对。正确做法是，只要某个格子被加入队列，就立刻把它在 visited 里标记为 true，而不是从队列里弹出时才标记。

原因很直接。BFS 是一层层扩散的，同一个格子可能同时被上下左右的邻居发现。如果你在入队时不标记，那这个格子可能被重复加入队列多次；等真正处理它的时候，队列里已经积压了大量相同坐标的冗余节点。地图小的时候看不出问题，地图一旦变成 1000×1000，队列会被撑爆，轻则超时，重则内存溢出。

所以代码里的标准动作是：

if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) { continue; } visited[nx][ny] = true; queue.offer(new int[]{nx, ny, step + 1});

visited 初始时全部为 false，起点在入队前就要标记为 true。我见过有人把visited[0][0] = true;漏掉，结果起点周围一圈的格子会因为再次走到起点而重复入队，样例也许能过，但用例一大就出问题。

2.3 高度差判断：绝对值还是单向爬升

题目里“高度差”这三个字最容易产生歧义。如果原题写的是“高度差的绝对值不超过 k”，那判断条件就是：

if (Math.abs(grid[nx][ny] - grid[x][y]) > k) { continue; }

如果原题写的是“每次爬升的高度不超过 k”，意思是下降不受限制，只有上升才看高度差，那判断条件要改成：

int diff = grid[nx][ny] - grid[x][y]; if (diff > k) { continue; }

下降时 diff 是负数，负数永远不大于 k，所以下降不受限制。这两种写法天差地别，但题面往往只有几个字的差别。遇到这种题，我习惯在读题时用笔把“绝对值”三个字圈出来，或者在代码旁边写一行注释，明确自己用的是哪种判断。考场上最亏的就是思路全对，但边界条件理解反了。

2.4 起点也可能就是答案

很多人初始化最高海拔时容易写成int maxH = 0;，如果地图里有负数海拔，这个初始值就会干扰结果。更稳的做法是把起点海拔作为初始最高值：

int maxH = grid[0][0]; int minStep = 0;

同时，步数要跟着初始化成 0。否则如果全图一个格子都走不出去，你最后输出的时候会得到错误结果。起点本身是可达的，而且步数一定是 0，这一点不需要任何扩展就能确认。

最高值的更新逻辑可以放在出队时：

if (grid[x][y] > maxH) { maxH = grid[x][y]; minStep = step; } else if (grid[x][y] == maxH && step < minStep) { minStep = step; }

由于 BFS 按层推进，第一次遇到某个最高海拔时，步数就已经是最短的；后面的 else if 分支更多是防御性写法，遇到多个同海拔格子时保证继续保留最小步数。

3. 完整 Java 实现：可直接抄到本地跑通的代码

3.1 代码主体

下面这份代码按标准 OJ 格式写，类名是 Main，使用 Scanner 读入，BFS 搜索，最后输出结果。

import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class Main { static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); int[][] grid = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { grid[i][j] = sc.nextInt(); } } boolean[][] visited = new boolean[n][m]; Queue<int[]> queue = new ArrayDeque<>(); visited[0][0] = true; queue.offer(new int[]{0, 0, 0}); int maxH = grid[0][0]; int minStep = 0; while (!queue.isEmpty()) { int[] cur = queue.poll(); int x = cur[0]; int y = cur[1]; int step = cur[2]; if (grid[x][y] > maxH) { maxH = grid[x][y]; minStep = step; } else if (grid[x][y] == maxH && step < minStep) { minStep = step; } for (int[] d : dirs) { int nx = x + d[0]; int ny = y + d[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; } if (visited[nx][ny]) { continue; } if (Math.abs(grid[nx][ny] - grid[x][y]) > k) { continue; } visited[nx][ny] = true; queue.offer(new int[]{nx, ny, step + 1}); } } System.out.println(maxH + " " + minStep); } }

这份代码默认输入顺序是“行数 n、列数 m、k”。如果你的题目顺序是“列数 m、行数 n”，读入时对应调整一下两个变量的赋值，别下意识把行列搞混。我在机考复盘里见过太多人因为输入顺序反了，导致数组越界。

3.2 用手工表格模拟一次 BFS 分层

继续用前面的样例3 3 1加矩阵0 1 2 / 3 2 1 / 0 0 1来看运行过程。队列变化大致如下：

后面队列可能还会处理一些海拔 1、0 的格子，但因为最高已经是 3，不会再更新答案。最终输出3 3。

看这个表格你会发现，BFS 真正强大之处在于“第一次扩展到的步数就是最短步数”。比如 (1,0) 这个海拔 3 的格子，它也可以从 (2,1) 上移到达，但从 (0,0) 到 (2,1) 本身就比从 (1,1) 到 (1,0) 多 1 步，所以从 (1,1) 这一路先到的就是最优解。

3.3 输出格式和返回值怎么确认

这类题目的输出有两种习惯，一种是输出一行两个整数，中间空格，例如3 3；另一种是输出两个整数，各占一行。C 卷通常是一行两个数，但我每次都建议你拿样例核对，别想当然。如果题目要求输出“最高海拔 最少步数”，那System.out.println(maxH + " " + minStep);就够了。如果你发现样例输出是两行，改成两次 println 就行。

还有一个细节：如果题目不要求输出步数，只问最高可达海拔，那么 minStep 的维护可以直接去掉。但根据“周末爬山”这个题名和常见题库记录，多数版本是要求输出两个值的，所以上面代码保留完整逻辑。遇到变体时，删减起来也很容易。

4. 机考实战：双机位环境下的提交流程与常见报错

4.1 无辅助编码能力比想象中重要

双机位考试的意思是，一台设备拍正面，一台设备拍侧面或者背后，全程监控。这种安排本身并不复杂，对大多数考生来说，真正受影响的是“没法切屏查资料”。平时在 IDEA 或者 VS Code 里写代码，自动补全能帮你把 import、数组声明、队列写法这些基础结构瞬间补全；一旦切到在线编辑器，这些便利全都没有了。

所以我的建议是：备考阶段，至少用纯文本编辑器手写十遍 BFS 模板。不是复制粘贴，而是新建一个空文件，从import java.util.*;开始敲。敲到 “Queue<int[]> queue = new ArrayDeque<>();” 这一步不再卡壳，机考时才不会慌张。这类题的代码量其实不大，难点全在“稳定默写”上。

4.2 提交前的自查清单

每次写完代码，别急着点提交，先按下面清单扫一遍：

• 类名是不是 Main。OD 机考一般要求主类名必须是 Main，大小写也不能错。
• 有没有写import java.util.*;。漏掉 import 会被编译错误直接卡住。
• 有没有去掉调试输出。System.out.println只能出现在你真正想输出的地方，不能用来打印“正在搜索”之类的信息。
• 输入的行列顺序对不对。题目给的是“n m k”还是“m n k”，要跟读入逻辑一一对应。
• 起点 visited 标记是否设置。漏掉它，队列里会出现大量冗余节点。
• k 的判断是Math.abs(diff) > k还是diff > k。读题时确认用哪种。
• 输出顺序是否是“海拔 步数”。有些题目顺序反着来，样例永远是验证标准。

这一套检查做完，最多花一分钟，但能避免大部分低级失分。

4.3 高频报错原因和对策

我把刷题群里常遇到的报错整理成了一张速查表，遇到问题直接对号入座。

这些错误里，最隐蔽的是最后两种。负数海拔这个点，很多题目样例不会覆盖，但隐藏测试可能给。k 判断方向就更不用说了，必须靠读题时圈关键词来规避。

5. 从“周末爬山”延伸出去：BFS 变体和进阶思路

5.1 多起点：多源 BFS 的写法

有些“爬山”类问题不会限定起点是左上角，而是说“可以从山脚任何一个入口出发”。这时候你只需要把所有入口坐标在初始阶段全部入队，并且全部标记为 visited，步数都设为 0。后面继续正常 BFS 即可。

多源 BFS 的本质是“虚拟超级起点”。想象有一个看不见的起点，它到所有入口的代价都是 0，那么问题就变回单源 BFS。这种思路在岛屿数量、腐烂的橘子、多源火灾蔓延等题目里非常常见。如果你能把“周末爬山”理解透，多源版本只需要在初始化队列的部分加一个 for 循环。

5.2 移动代价不再是 1：换成 Dijkstra

如果题目改成“往上爬一步消耗 2 体力，往下走一步消耗 1 体力”，然后问你最少消耗多少体力到达最高峰，普通 BFS 就不适用了。因为 BFS 默认每一步代价相同，而这里每一步的代价取决于方向。

这种情况要把队列换成优先队列，按累计代价从小到大取出节点，相当于 Dijkstra 算法。Java 里可以这样写：

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);

数组第三位存累计体力消耗，每次更新时把这一步的消耗加上去。visited 也不再是简单的布尔值，因为第一次到达某个格子的路径消耗不一定是最小的，你需要用一个 int 数组记录当前最优消耗，或者让优先队列自然淘汰更差的路径。

C 卷如果考到这种加权版本，题面一定会有“体力”“代价”等明确字眼。冲刺高分的话值得准备一下，但基础版本更要吃透。

5.3 大矩阵下的内存优化技巧

如果 n 和 m 都达到了 1000，二维 boolean 的 visited 占用大约 1MB，完全没问题。但如果你想让代码更紧凑，可以把二维坐标压缩成一维索引idx = x * m + y，队列里只存 idx 和 step。需要取出坐标时，再用x = idx / m; y = idx % m;还原。这样能减少一点数组对象引用，但可读性会下降。

我一般不推荐在考试中用这种优化，除非内存限制特别紧张。大部分 OJ 对这道题的设置都足够宽松，boolean[n][m]就是最稳妥、最不容易写错的选择。代码清晰比省几百 KB 内存更重要，因为考试看的是正确率，不是炫耀技巧。

6. 做完这题后，值得记住的三个习惯

第一，读题时把边界条件全部圈出来。是“绝对值”还是“只限制爬升”？输出顺序是“海拔 步数”还是反过来？起点能不能作为最高峰？这些都要写在纸上，而不是靠脑子记。人一紧张，记忆会骗人，白纸黑字不会。

第二，BFS 的 visited 标记永远和入队绑定。写代码时先写visited[nx][ny] = true;，再写queue.offer(...)，顺序不要反过来。只要遵循这个习惯，队列就不会出现重复节点，超时问题会少一大半。

第三，提交前给自己留一分钟做静态自查。我会把样例再读一遍，然后重新看一眼 k 的判断和输出语句。这个方法救过我很多次，包括这一次复盘“周末爬山”时也帮我抓到了行列读反的问题。

我现在刷网格搜索题的习惯是：先在草稿纸上画一张小的可达性表，用人肉 BFS 模拟一遍，再落到代码。这个习惯就是从这道题开始的——很多边界问题不是写出来的，是自己推演的。希望这篇文章能帮你把“周末爬山”一次写对，也让 BFS 模板变成你考场上最不慌的那部分。