【华为OD机试真题】亲子游戏 · 最短路径拿最多糖果（Java/Go）
·
一、题目
题目描述：
宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
输入描述：
第一行输入为 N，N 标识二维矩阵的大小
之后 N 行，每行有 N 个值，表格矩阵每个位置的值其中：
- -3：妈妈
- -2：宝宝
- -1：障碍0：糖果数（0 表示没有糖果，但是可以走）
- ≥0：糖果数(0表示没有糖果，但是可以走)
输出描述：
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格备注：
地图最大 50*50示例1：
输入：
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3输出：
9说明：
此地图有两条最短路径可到宝宝位置，都是最短路径6步，但先向下再向左可以拿到9个糖果示例2：
输入：
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3
输出：
-1
说明：
此地图妈妈无法到达宝宝位置
二、题目深度解析🧠
1. 核心矛盾
通常的 BFS 只关心“是否到达”或“最短步数”。但本题增加了第二维度的约束：在步数最短的前提下，最大化路径权值和。
- 第一优先级：时间（步数）最短。
- 第二优先级：糖果数量最多。
2. 为什么不能直接用 Dijkstra？
虽然 Dijkstra 可以处理带权最短路，但本题的“权值”有两个维度：
- 边的权重恒为 1（步数）。
- 点的权重不同（糖果数）。
由于边权为 1，BFS 天然保证第一次到达某点时的步数是最小的。因此，我们不需要复杂的优先队列，只需在 BFS 过程中维护一个maxCandy[x][y]数组即可。
3. 解题策略：BFS + 贪心更新
- 状态定义：
dist[x][y]记录到达(x, y)的最短步数，candy[x][y]记录在最短步数下能拿到的最大糖果数。 - 初始化：
dist全为无穷大，candy全为 -1。起点candy设为起点的糖果数（注意起点是 -3，需特殊处理，视为 0 糖果或根据题意，通常起点不计入糖果，只计路上的，但本题示例暗示起点和终点的数值可能只是标记，实际糖果看 >=0 的值。修正：根据示例1，起点 -3 和终点 -2 所在的格子如果不含正数糖果，通常不计分，或者题目隐含 -3/-2 位置本身没有额外糖果，只有 >=0 的格子有。观察示例1：- 路径：(0,3)[-3] -> (1,3)[1] -> (1,2)[1] -> (2,2)[-1 障碍, 不通] ...
- 让我们重新推导示例1的逻辑：
- 起点 (0,3)，终点 (3,0)。
- 路径1：(0,3)→(0,2)[1]→(0,1)[2]→(0,0)[3]→(1,0)[1]→(2,0)[1]→(3,0)[-2]。步数6。糖果：1+2+3+1+1 = 8? 不对，答案是9。
- 路径2（说明中提到“先向下再向左”）：(0,3)→(1,3)[1]→(2,3)[2]→(3,3)[3]→(3,2)[2]→(3,1)[1]→(3,0)[-2]。
- 糖果计算：1(1,3) + 2(2,3) + 3(3,3) + 2(3,2) + 1(3,1) = 9。
- 结论：起点(-3)和终点(-2)本身不计入糖果数，只计算路径上
>=0的格子。
- 更新规则：
当从curr扩展到next时：- 若
next未访问过（dist[next] == INF）：- 更新
dist[next] = dist[curr] + 1 - 更新
candy[next] = candy[curr] + getVal(next) next入队。
- 更新
- 若
next已访问过，且dist[next] == dist[curr] + 1（说明找到了另一条同样短的路）：- 如果
candy[curr] + getVal(next) > candy[next]：- 更新
candy[next]为更大值。 - 关键点：此时
next需要再次入队吗？- 不需要再次入队去更新它的子节点吗？
- 需要！ 因为
next的糖果数变大了，它传递给后续节点的糖果基数也变大了。所以必须将next再次加入队列（或者在同类层处理中传播），以便更新其后续路径的最大值。 - 优化策略：标准的 BFS 每个点只出队一次。但在“最短路最大权值”问题中，如果在同一层发现更优解，通常需要允许该点再次入队，或者使用类似 SPFA 的思想，但因为边权为 1，我们可以限制只在
dist相等且candy变大时入队。考虑到 N≤50N≤50 ，数据量小，即使稍微冗余的入队也能轻松通过。
- 更新
- 如果
- 若
三、Java 实现 (面向对象风格)💻
Java 版本利用内部类 Point 封装坐标，代码结构清晰，适合工程化场景。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
// 方向数组：上下左右
private static final int[] DX = {-1, 1, 0, 0};
private static final int[] DY = {0, 0, -1, 1};
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
if (!scanner.hasNextInt()) return;
int n = scanner.nextInt();
int[][] grid = new int[n][n];
int startX = -1, startY = -1;
int endX = -1, endY = -1;
// 读取矩阵并定位起点终点
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = scanner.nextInt();
if (grid[i][j] == -3) {
startX = i;
startY = j;
} else if (grid[i][j] == -2) {
endX = i;
endY = j;
}
}
}
System.out.println(solve(n, grid, startX, startY, endX, endY));
}
private static int solve(int n, int[][] grid, int sx, int sy, int ex, int ey) {
// dist[i][j]: 到达 (i,j) 的最短步数
int[][] dist = new int[n][n];
// maxCandy[i][j]: 在最短步数下，到达 (i,j) 的最大糖果数
int[][] maxCandy = new int[n][n];
// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = Integer.MAX_VALUE;
maxCandy[i][j] = -1;
}
}
Queue<Point> queue = new LinkedList<>();
// 起点初始化
dist[sx][sy] = 0;
maxCandy[sx][sy] = 0; // 起点本身不计糖果
queue.offer(new Point(sx, sy));
while (!queue.isEmpty()) {
Point curr = queue.poll();
int cx = curr.x;
int cy = curr.y;
// 如果已经到达终点，我们不能直接break，因为可能有同步数的其他路径糖果更多
// 但因为是BFS，第一次遇到终点时的步数一定是最小的。
// 我们需要继续处理完当前层所有可能更新终点的情况，或者允许终点多次入队更新最大值。
// 这里采用通用策略：只要找到更优解就入队。
for (int i = 0; i < 4; i++) {
int nx = cx + DX[i];
int ny = cy + DY[i];
// 边界检查
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
// 障碍物检查
if (grid[nx][ny] == -1) continue;
int step = dist[cx][cy] + 1;
int candyGain = (grid[nx][ny] >= 0) ? grid[nx][ny] : 0;
int newCandy = maxCandy[cx][cy] + candyGain;
// 情况1: 第一次到达该点 (找到更短路径)
if (step < dist[nx][ny]) {
dist[nx][ny] = step;
maxCandy[nx][ny] = newCandy;
queue.offer(new Point(nx, ny));
}
// 情况2: 以相同步数到达，但糖果更多
else if (step == dist[nx][ny] && newCandy > maxCandy[nx][ny]) {
maxCandy[nx][ny] = newCandy;
// 重要：糖果数更新了，需要重新入队，以便将更大的糖果数传递给后续节点
queue.offer(new Point(nx, ny));
}
}
}
if (dist[ex][ey] == Integer.MAX_VALUE) {
return -1;
}
return maxCandy[ex][ey];
}
}✅ Java 版亮点
- 封装性：使用
Point类管理坐标，代码可读性强。 - 逻辑严密：处理了
step == dist且candy更大的情况，并重新入队，确保最优解能传递到终点。 - 健壮性：完善的边界和障碍物判断。
四、Go 语言实现 (原生高性能风格)🚀
Go 版本利用 struct 和 slice 模拟队列，无依赖，运行效率极高，非常适合对性能敏感的机考环境。
package main
import (
"fmt"
"math"
)
type Point struct {
x, y int
}
func main() {
var n int
if _, err := fmt.Scan(&n); err != nil {
return
}
grid := make([][]int, n)
startX, startY, endX, endY := -1, -1, -1, -1
for i := 0; i < n; i++ {
grid[i] = make([]int, n)
for j := 0; j < n; j++ {
fmt.Scan(&grid[i][j])
if grid[i][j] == -3 {
startX, startY = i, j
} else if grid[i][j] == -2 {
endX, endY = i, j
}
}
}
result := solve(n, grid, startX, startY, endX, endY)
fmt.Println(result)
}
func solve(n int, grid [][]int, sx, sy, ex, ey int) int {
// 初始化距离和糖果数组
dist := make([][]int, n)
maxCandy := make([][]int, n)
for i := 0; i < n; i++ {
dist[i] = make([]int, n)
maxCandy[i] = make([]int, n)
for j := 0; j < n; j++ {
dist[i][j] = math.MaxInt32
maxCandy[i][j] = -1
}
}
// 手动实现队列
queue := make([]Point, 0)
queue = append(queue, Point{x: sx, y: sy})
dist[sx][sy] = 0
maxCandy[sx][sy] = 0
dx := []int{-1, 1, 0, 0}
dy := []int{0, 0, -1, 1}
head := 0
for head < len(queue) {
curr := queue[head]
head++ // 出队
cx, cy := curr.x, curr.y
for i := 0; i < 4; i++ {
nx := cx + dx[i]
ny := cy + dy[i]
// 边界检查
if nx < 0 || nx >= n || ny < 0 || ny >= n {
continue
}
// 障碍物
if grid[nx][ny] == -1 {
continue
}
step := dist[cx][cy] + 1
gain := 0
if grid[nx][ny] >= 0 {
gain = grid[nx][ny]
}
newCandy := maxCandy[cx][cy] + gain
// 发现更短路径
if step < dist[nx][ny] {
dist[nx][ny] = step
maxCandy[nx][ny] = newCandy
queue = append(queue, Point{x: nx, y: ny})
} else if step == dist[nx][ny] && newCandy > maxCandy[nx][ny] {
// 同步数但糖果更多，更新并入队
maxCandy[nx][ny] = newCandy
queue = append(queue, Point{x: nx, y: ny})
}
}
}
if dist[ex][ey] == math.MaxInt32 {
return -1
}
return maxCandy[ex][ey]
}✅ Go 版亮点
- 零开销抽象：直接使用
slice作为队列，配合head指针，避免了container/list的指针跳转开销。 - 内存紧凑：
dist和maxCandy使用二维切片，内存布局连续，缓存友好。 - 逻辑一致：完美复刻了核心算法，处理了重复入队逻辑。
五、关键逻辑推演 (以示例1为例)🔍
输入地图：
3 2 1 -3(起)
1 -1 1 1
1 1 -1 2
-2(终) 1 2 3- Start: (0,3), Step=0, Candy=0. 入队。
- Layer 1:
- (0,2): Step=1, Candy=1.
- (1,3): Step=1, Candy=1.
- Layer 2:
- 从 (0,2) -> (0,1)[2]: Step=2, Candy=1+2=3.
- 从 (1,3) -> (2,3)[2]: Step=2, Candy=1+2=3.
- ...
- 关键分歧点:
- 假设某点
P可以通过路径 A (Step=3, Candy=5) 到达，也可以通过路径 B (Step=3, Candy=8) 到达。 - BFS 先处理路径 A，
dist[P]=3,candy[P]=5，P 入队。 - 随后处理路径 B，发现
step==3但8 > 5，更新candy[P]=8，P 再次入队。 - 当 P 第二次出队时，它会带着 8 个糖果去更新它的邻居，从而保证最终结果是最优的。
- 假设某点
结果验证：
示例1中，向下走的路径累积糖果更多，算法会正确捕捉到这一差异，输出 9。
示例2中，障碍物阻断所有路径，dist 保持无穷大，输出 -1。
六、避坑指南⚠️
- 起点/终点数值处理：
- 题目中 -3 和 -2 只是标记，不要把它们加到糖果总数里！只有
>=0的数字才代表糖果。代码中已通过if grid[nx][ny] >= 0严格过滤。
- 题目中 -3 和 -2 只是标记，不要把它们加到糖果总数里！只有
- 重复入队死循环：
- 有人会担心
step == dist且candy更新会导致死循环。 - 不会。因为糖果数是单调递增的，且网格有限，每个点的
maxCandy更新次数是有限的（最多等于到达该点的路径数，实际上远小于此）。对于 50×5050×50 的地图，完全不会超时。
- 有人会担心
- 不可达判断：
- 最后一定要检查
dist[ex][ey]是否仍为初始化的最大值，若是则输出 -1。
- 最后一定要检查
七、复杂度分析📊
- 时间复杂度： O(K⋅N2) 。
- 在最坏情况下，每个点可能会因为糖果数更新而多次入队。但在网格图中，这个系数 KK 很小。对于 N=50 ，运算量在万级别，毫秒级完成。
- 空间复杂度： O(N2) 。
- 用于存储
dist,maxCandy数组和队列。
- 用于存储
八、结语
这道题是 BFS 最短路模型 的经典变种，考察了候选人对 状态多维更新 的理解。
- Java 开发者可以学习如何在对象模型下优雅地处理状态转移。
- Go 开发者可以体验如何用极简的原生语法实现高效算法。
掌握这种 "最短路 + 最大权值" 的模板，无论是应对华为 OD、大厂笔试，还是实际工作中的路径规划问题，都能游刃有余。
觉得有帮助请 点赞👍、收藏⭐、关注🙋！后续将带来更多 机考真题全语言解析 系列！
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
13
0- 0
已为社区贡献19条内容
所有评论(0)