不积跬步，无以至千里。（荀子·劝学）
目录
- 华为OD机试 -【亲子糖果赛】题目：
- 题目解析：
- 使用JS/NodeJS代码解答：
- 代码逐行解读：
华为OD机试 -【亲子糖果赛】题目：
宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
输入描述：
第一行输入为 N，N 表示二维矩阵的大小
之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：
-3：妈妈
-2：宝宝
-1：障碍
≥0：糖果数（0表示没有糖果，但是可以走）
输出描述：
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格。
示例1输入：
43 2 1 -31 -1 1 11 1 -1 2-2 1 2 3
输出：
9
题目解析：
这个问题通常用BFS来解决，因为BFS适合寻找最短路径。 但还需要在相同步数的情况下，选择糖果最多的路径。我们需要使用一个二维数组来记录到达每个位置时的最大糖果数，同时记录步数。这样，在BFS的过程中，如果遇到更优的路径（即相同步数但糖果更多），可以更新这个记录。
现在，如何实现这一点？
- 首先，遍历矩阵，找到妈妈和宝宝的位置。即遍历每个格子，记录值为-3的位置作为起点，值为-2的位置作为终点。
- 然后，初始化一个二维数组，记录每个位置的最大糖果数和到达该位置所需的步数。例如，创建一个结构，每个元素包含当前最大的糖果数和对应的步数。初始时，所有位置的糖果数为-1，步数为无穷大（或者一个很大的数）。起点的糖果数为0，步数为0。
- 使用队列进行BFS。队列中的每个元素包含当前坐标x、y，当前的总糖果数，当前的步数。
- 对于每个出队的节点，检查四个方向。对于每个方向的新坐标，检查是否越界，是否是障碍物。如果是障碍物，跳过。否则，计算新的糖果数：如果该格子的值>=0，则新的糖果数是当前糖果数加上该值；否则，新的糖果数是当前糖果数（比如，遇到-3或-2的情况）。新的步数是当前步数+1。
- 然后，检查该新坐标是否已经被访问过：
- 如果从未被访问过（即步数为无穷大），则更新该位置的糖果数和步数，并将该节点入队。
- 如果已经被访问过，但新步数比之前的步数更小，则更新糖果数和步数，并重新入队，因为更短的路径可能带来不同的糖果数。
- 如果新步数等于之前的步数，但新的糖果数比之前的更大，则更新糖果数为较大的值，并重新入队，因为同一时间步数下可能有更大的糖果数。
现在，具体步骤：
- 读取输入，解析N，然后读取N行，每行N个数值，构成二维数组grid。
- 找到妈妈的位置（-3）和宝宝的位置（-2），记录为start和end。
- 如果start或end不存在，或者start等于end，或者无法到达（障碍物阻挡等情况），则返回-1。
- 创建一个二维数组visited，每个元素保存到达该位置时的最大糖果数和步数。初始时，所有位置的steps为Infinity，candies为-1。start位置的steps为0，candies为0。
- 使用队列进行BFS。初始时，将start的位置入队，记录candies为0，steps为0。
- 对于队列中的每个节点，处理四个方向：
a. 检查是否越界，是否是障碍物（grid为-1），如果是，跳过。
b. 算新位置的糖果数：如果该位置的grid值>=0，则新的糖果数是当前candies + grid值；否则，新的糖果数是当前candies（比如-3、-2的情况）
c. 计算新steps = current.steps +1。
d. 检查新位置是否已经可以被更优的路径访问过：
i. 如果新steps < visited的steps：说明这是更短的路径，需要更新，并加入队列。
ii. 如果新steps == visited的steps，但新的candies > visited的candies：说明同一时间更优的糖果数，需要更新，并加入队列。
iii. 否则，不处理。 - 当处理到end的位置时，记录当前的candies，但继续处理队列中的其他可能路径，因为可能存在同一时间步数下的更高糖果数。
- 最终，如果end的位置的steps是Infinity，说明无法到达，返回-1。否则，返回end位置的candies的最大值。
使用JS/NodeJS代码解答：
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let N, grid = [], lineCount = 0;rl.on('line', (line) => {if (!N) {N = parseInt(line);} else {const row = line.trim().split(' ').map(Number);if (row.length !== N) {console.error(-1);process.exit(1);}grid.push(row);lineCount++;if (lineCount === N) {rl.close();processInput();}}
});function processInput () {// 定位起点终点let mom, baby;grid.forEach((row, i) => {row.forEach((val, j) => {if (val === -3) mom = [i, j];if (val === -2) baby = [i, j];});});// BFS算法实现console.log(bfs(mom, baby));
}function bfs (start, end) {const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];const [startX, startY] = start;const visited = Array.from({ length: N }, () => Array(N).fill(false));const queue = [[startX, startY, 0]]; // [x, y, candies]let max = -Infinity;const [endX, endY] = end;visited[startX][startY] = true;while (queue.length) {const [x, y, candies] = queue.shift();if (x === endX && y === endY) {max = Math.max(max, candies);continue;}for (const [dx, dy] of dirs) {const nx = x + dx;const ny = y + dy;if (nx >= 0 && nx < N && ny >= 0 && ny < N&& !visited[nx][ny]&& grid[nx][ny] !== -1) {visited[nx][ny] = true;queue.push([nx, ny, candies + Math.max(0, grid[nx][ny])]);}}}return max !== -Infinity ? max : -1;
}
正确解答：
输入一行数不对的情况：
妈妈根本无法到达孩子的情况：
代码逐行解读：
- 引入Node.js的readline模块，用于从标准输入（通常是键盘）读取数据。
const readline = require('readline');
- 创建一个readline接口实例rl，配置其输入和输出分别为标准输入和标准输出。
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});
- 声明变量N（将用于存储网格的大小），grid（一个空数组，将用于存储网格的行），以及lineCount（用于跟踪已读取的行数）。
let N, grid = [], lineCount = 0;
- 为rl接口注册一个’line’事件监听器，每当从标准输入读取一行时都会触发。
rl.on('line', (line) => {
- 如果N未定义（即第一次读取行时），则将其设置为当前行的整数值（网格的大小）。否则，执行else分支。
if (!N) {N = parseInt(line);} else {
- 去除行的首尾空格，然后按空格分割成字符串数组，并使用map(Number)将每个字符串转换为数字，得到网格的一行。
const row = line.trim().split(' ').map(Number);
- 检查当前行的长度是否与网格的大小N相等。如果不等，打印-1并退出程序。
if (row.length !== N) {console.error(-1);process.exit(1);}
- 将当前行添加到grid数组中，并增加lineCount。
grid.push(row);lineCount++;
- 如果已读取的行数等于网格的大小N，则关闭rl接口并调用processInput函数来处理输入数据。
if (lineCount === N) {rl.close();processInput();}}
});
- 定义processInput函数，用于处理输入数据。
function processInput () {
- 声明变量mom和baby，将用于存储起点（妈妈的位置）和终点（宝宝的位置）。
let mom, baby;
- 遍历grid数组的每一行和每个单元格。保存mom和baby的坐标。
grid.forEach((row, i) => {row.forEach((val, j) => {if (val === -3) mom = [i, j];if (val === -2) baby = [i, j];});});
- 调用bfs函数，传入起点和终点坐标，并打印返回的结果。
console.log(bfs(mom, baby));
}
- 定义bfs函数，实现广度优先搜索算法。声明一个方向数组dirs，包含四个方向（上、下、左、右）的坐标变化量。
function bfs (start, end) {const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
- 解构起点坐标，初始化一个visited数组用于跟踪访问过的单元格，初始化一个队列queue用于存储待访问的单元格和当前路径上的糖果数，初始化max为-Infinity用于存储最大糖果数，解构终点坐标。
const [startX, startY] = start;const visited = Array.from({ length: N }, () => Array(N).fill(false));const queue = [[startX, startY, 0]]; // [x, y, candies]let max = -Infinity;const [endX, endY] = end;
- 将起点标记为已访问。
visited[startX][startY] = true;
- 当队列不为空时，执行循环。
while (queue.length) {
- 从队列中取出一个单元格和其路径上的糖果数。
const [x, y, candies] = queue.shift();
- 如果当前单元格是终点，则更新max为当前路径上的糖果数和max中的较大值，并继续下一次循环。
if (x === endX && y === endY) {max = Math.max(max, candies);continue;}
- 遍历四个方向。
for (const [dx, dy] of dirs) {
- 计算相邻单元格的坐标。
const nx = x + dx;const ny = y + dy;
- 检查相邻单元格是否在网格范围内、是否未访问过、并且不是障碍物（-1表示障碍物）。
if (nx >= 0 && nx < N && ny >= 0 && ny < N&& !visited[nx][ny]&& grid[nx][ny] !== -1) {
- 将相邻单元格标记为已访问，并将其添加到队列中，同时更新路径上的糖果数。
visited[nx][ny] = true;queue.push([nx, ny, candies + Math.max(0, grid[nx][ny])]);}}}
- 如果找到了到达终点的路径，则返回最大糖果数；否则返回-1。
return max !== -Infinity ? max : -1;
}