一、题目题目描述宝宝和妈妈参加亲子游戏在一个二维矩阵N*N的格子地图上宝宝和妈妈抽签决定各自的位置地图上每个格子有不同的糖果数量部分格子有障碍物。游戏规则是妈妈必须在最短的时间每个单位时间只能走一步到达宝宝的位置路上的所有糖果都可以拿走不能走障碍物的格子只能上下左右走。请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果优先考虑最短时间到达的情况下尽可能多拿糖果。输入描述第一行输入为 NN 标识二维矩阵的大小之后 N 行每行有 N 个值表格矩阵每个位置的值其中-3妈妈-2宝宝-1障碍0糖果数0 表示没有糖果但是可以走≥0糖果数(0表示没有糖果但是可以走)输出描述输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果行末无多余空格备注地图最大 50*50示例1输入43 2 1 -31 -1 1 11 1 -1 2-2 1 2 3输出9说明此地图有两条最短路径可到宝宝位置都是最短路径6步但先向下再向左可以拿到9个糖果示例2输入43 2 1 -3-1 -1 1 11 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 会稍大但在实际网格图中通常很小。对于 N50 总操作数远低于 107 可在 100ms 内完成。空间复杂度 O(N2) 。用于存储dist、max_candy数组和队列。八、总结无论是Python的快速开发还是JavaScript的全栈适用性解决这类问题的核心都在于对BFS 状态的精细控制。Python 选手享受deque和列表推导式带来的快感代码量少逻辑直观。JS 选手掌握readline异步流处理是机考通关的关键数组模拟队列能让你在 V8 引擎下跑得飞快。希望这篇博文能助你顺利拿下华为 OD 机考如果觉得有用请点赞、收藏⭐、评论支持一下