当前位置：首页 > news >正文

【华为OD机试真题】亲子游戏 · 最短路径拿最多糖果 (Python /JS)

news 2026/8/20 16:25:21

一、题目

题目描述：
宝宝和妈妈参加亲子游戏，在一个二维矩阵（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
说明：
此地图妈妈无法到达宝宝位置

二、题目深度解析🧠

这道题的本质是带权最短路问题的变种，但有两个特殊的约束：

第一优先级：路径长度（步数）必须最短。
第二优先级：在步数相同的所有路径中，选择经过格子糖果数之和最大的那条。

💡 解题思路

普通的 BFS 只能找到最短步数，无法直接处理“最大权值”。我们需要对标准 BFS 进行改造：

双状态数组：
- dist[x][y]：记录到达(x, y)的最小步数。
- max_candy[x][y]：记录在最小步数前提下，到达(x, y)的最大糖果数。
松弛操作（Relaxation）的变种：
当从当前点curr扩展到邻居next时：
- 情况 A（发现更短路径）：如果dist[next] > dist[curr] + 1，说明我们找到了一条更快的路。
  - 更新dist[next]和max_candy[next]。
  - 将next入队。
- 情况 B（发现同等步数但更多糖果）：如果dist[next] == dist[curr] + 1且new_candy > max_candy[next]。
  - 更新max_candy[next]为更大的值。
  - 关键点：此时必须将next再次入队！因为next的糖果基数变大了，它后续能传递给子节点的糖果总数也会变大。如果不重新入队，后续节点可能基于旧的、较小的糖果数进行计算，导致最终结果错误。
终止条件：
- 队列空时结束。
- 若终点的dist仍为初始无穷大，说明不可达，返回-1。

三、Python 实现 (简洁高效风)

Python 凭借其简洁的语法和强大的标准库collections，是解决此类算法题的神器。

import sys from collections import deque def solve(): # 读取所有输入 input_data = sys.stdin.read().split() if not input_data: return iterator = iter(input_data) try: n = int(next(iterator)) except StopIteration: return grid = [] start_pos = None end_pos = None # 解析矩阵 for i in range(n): row = [] for j in range(n): val = int(next(iterator)) row.append(val) if val == -3: start_pos = (i, j) elif val == -2: end_pos = (i, j) grid.append(row) if not start_pos or not end_pos: print("-1") return sx, sy = start_pos ex, ey = end_pos # 初始化状态数组 # dist[i][j] 存储最短步数，初始化为无穷大 dist = [[float('inf')] * n for _ in range(n)] # max_candy[i][j] 存储最短步数下的最大糖果数，初始化为 -1 max_candy = [[-1] * n for _ in range(n)] # 方向数组：上下左右 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 队列初始化 queue = deque() queue.append((sx, sy)) dist[sx][sy] = 0 max_candy[sx][sy] = 0 # 起点本身不计糖果 while queue: cx, cy = queue.popleft() current_step = dist[cx][cy] current_candy = max_candy[cx][cy] for dx, dy in directions: nx, ny = cx + dx, cy + dy # 边界检查 if 0 <= nx < n and 0 <= ny < n: # 障碍物检查 if grid[nx][ny] == -1: continue # 计算新状态的步数和糖果数 new_step = current_step + 1 # 只有 >=0 的格子才有糖果，-2(宝宝)和-3(妈妈)位置不计入额外糖果 gain = grid[nx][ny] if grid[nx][ny] >= 0 else 0 new_candy = current_candy + gain # 情况1: 找到更短的路径 if new_step < dist[nx][ny]: dist[nx][ny] = new_step max_candy[nx][ny] = new_candy queue.append((nx, ny)) # 情况2: 路径长度相同，但糖果更多 elif new_step == dist[nx][ny] and new_candy > max_candy[nx][ny]: max_candy[nx][ny] = new_candy # 重要：糖果数更新，需要重新入队以更新后续节点 queue.append((nx, ny)) # 检查结果 if dist[ex][ey] == float('inf'): print("-1") else: print(max_candy[ex][ey]) if __name__ == "__main__": solve()

✅ Python 版亮点

输入处理：使用sys.stdin.read().split()一次性读取所有令牌，避免了input()在多行输入时的繁琐和潜在的性能问题，非常适合处理矩阵类题目。
数据结构：collections.deque提供了 O(1) 的队头弹出操作，比list.pop(0)高效得多。
逻辑清晰：利用元组(x, y)直接作为队列元素，代码极其精简。

四、JavaScript (Node.js) 实现 (异步流处理)🌐

在 Node.js 环境中，处理标准输入（stdin）通常是异步的。很多初学者容易在这里踩坑（如数据未读完就开始计算）。本方案采用完整缓冲 + 同步解析的策略，确保稳健性。

javascript

编辑

const readline = require('readline'); function main() { const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); const lines = []; // 监听每一行输入 rl.on('line', (line) => { lines.push(line.trim()); }); // 输入结束时处理逻辑 rl.on('close', () => { // 将所有行合并并按空格分割成令牌数组 const tokens = lines.join(' ').split(/\s+/).filter(t => t !== ''); if (tokens.length === 0) return; let idx = 0; const n = parseInt(tokens[idx++], 10); const grid = []; let startX = -1, startY = -1; let endX = -1, endY = -1; // 构建矩阵并定位起点终点 for (let i = 0; i < n; i++) { const row = []; for (let j = 0; j < n; j++) { const val = parseInt(tokens[idx++], 10); row.push(val); if (val === -3) { startX = i; startY = j; } else if (val === -2) { endX = i; endY = j; } } grid.push(row); } if (startX === -1 || endX === -1) { console.log("-1"); return; } const result = solve(n, grid, startX, startY, endX, endY); console.log(result); }); } function solve(n, grid, sx, sy, ex, ey) { // 初始化距离和糖果数组 // 使用 Number.MAX_SAFE_INTEGER 表示无穷大 const INF = Number.MAX_SAFE_INTEGER; const dist = Array.from({ length: n }, () => Array(n).fill(INF)); const maxCandy = Array.from({ length: n }, () => Array(n).fill(-1)); // 方向数组 const dx = [-1, 1, 0, 0]; const dy = [0, 0, -1, 1]; // 模拟队列: [ {x, y} ] const queue = []; queue.push({ x: sx, y: sy }); dist[sx][sy] = 0; maxCandy[sx][sy] = 0; let head = 0; while (head < queue.length) { const curr = queue[head++]; // 出队 const { x: cx, y: cy } = curr; for (let i = 0; i < 4; i++) { const nx = cx + dx[i]; const ny = cy + dy[i]; // 边界检查 if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 障碍物检查 if (grid[nx][ny] === -1) continue; const newStep = dist[cx][cy] + 1; const gain = grid[nx][ny] >= 0 ? grid[nx][ny] : 0; const newCandy = maxCandy[cx][cy] + gain; // 情况1: 找到更短路径 if (newStep < dist[nx][ny]) { dist[nx][ny] = newStep; maxCandy[nx][ny] = newCandy; queue.push({ x: nx, y: ny }); } // 情况2: 步数相同但糖果更多 else if (newStep === dist[nx][ny] && newCandy > maxCandy[nx][ny]) { maxCandy[nx][ny] = newCandy; // 重新入队以传播更大的糖果值 queue.push({ x: nx, y: ny }); } } } if (dist[ex][ey] === INF) { return -1; } return maxCandy[ex][ey]; } main();

✅ JavaScript 版亮点

健壮的输入流：通过rl.on('close')确保所有数据读取完毕后再开始解析，完美应对多行输入的机考环境。
数组模拟队列：使用head指针配合push，避免了shift()操作带来的 O(N) 时间复杂度开销，保证队列操作为 O(1) 。
清晰的逻辑结构：将输入解析与核心算法分离，便于调试和维护。

五、深度解析：为什么需要“重复入队”？🔍

这是本题最容易出错的地方。让我们看一个简化的例子：

假设地图如下（数字代表糖果）：

S(0) -> A(10) -> C \ ^ -> B(5) -/

路径 1:S -> A -> C。到达A时步数=1，糖果=10。A入队。
路径 2:S -> B -> A。到达A时步数=2。这比路径 1 慢，忽略。

但在本题的特殊场景中：
假设存在两条步数相同的路径到达A：

路径 1:S -> X -> A(步数2, 糖果5)。先被处理，dist[A]=2,candy[A]=5。A入队。
路径 2:S -> Y -> A(步数2, 糖果8)。后被处理。
- 检测到dist[A] == 2(相等)。
- 检测到8 > 5(更优)。
- 操作：更新candy[A] = 8，并将A再次入队。

如果不重新入队会发生什么？
当A第一次出队（糖果=5）时，它已经去更新了C（假设C有 10 个糖果，则C的糖果变为 15）。
如果A不第二次出队，C永远不知道A其实可以带着 8 个糖果过来（那样C应该是 18）。
结论：为了将“更优的局部解”传播到全局，必须允许节点在同层最优解更新时重复入队。

六、常见陷阱与注意事项⚠️

起点和终点的值：
- 题目中-3(妈妈) 和-2(宝宝) 仅仅是标记。
- 切勿将它们加到糖果总数中！代码中通过grid[nx][ny] >= 0 ? grid[nx][ny] : 0完美规避了这个问题。
死循环风险：
- 有人担心重复入队会导致死循环。
- 不会。因为max_candy是单调递增的，且网格中糖果总数有限，每个格子的更新次数是有上限的。对于 50×50 的地图，运算量完全可控。
不可达处理：
- 务必检查终点是否被访问过（dist是否为初始值）。如果是，输出-1。

七、复杂度分析📊

时间复杂度： O(K⋅N2) 。
- N 是地图边长。
- K 是每个节点平均入队次数。在最坏情况下（如螺旋状更新）， KK 会稍大，但在实际网格图中通常很小。对于 N=50 ，总操作数远低于 107 ，可在 100ms 内完成。
空间复杂度： O(N2) 。
- 用于存储dist、max_candy数组和队列。