编程题 - 亲子糖果赛【JavaScript/Node.js解法】

不积跬步，无以至千里。（荀子·劝学）

华为OD机试 -【亲子糖果赛】题目：

宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。

游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。

输入描述：
第一行输入为 N，N 表示二维矩阵的大小
之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：
-3：妈妈
-2：宝宝
-1：障碍
≥0：糖果数（0表示没有糖果，但是可以走）
输出描述：
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格。

示例1输入：

4

3 2 1 -3

1 -1 1 1

1 1 -1 2

-2 1 2 3

输出：

9

题目解析：

这个问题通常用BFS来解决，因为BFS适合寻找最短路径。 但还需要在相同步数的情况下，选择糖果最多的路径。我们需要使用一个二维数组来记录到达每个位置时的最大糖果数，同时记录步数。这样，在BFS的过程中，如果遇到更优的路径（即相同步数但糖果更多），可以更新这个记录。
现在，如何实现这一点？

• 首先，遍历矩阵，找到妈妈和宝宝的位置。即遍历每个格子，记录值为-3的位置作为起点，值为-2的位置作为终点。
• 然后，初始化一个二维数组，记录每个位置的最大糖果数和到达该位置所需的步数。例如，创建一个结构，每个元素包含当前最大的糖果数和对应的步数。初始时，所有位置的糖果数为-1，步数为无穷大（或者一个很大的数）。起点的糖果数为0，步数为0。
• 使用队列进行BFS。队列中的每个元素包含当前坐标x、y，当前的总糖果数，当前的步数。
• 对于每个出队的节点，检查四个方向。对于每个方向的新坐标，检查是否越界，是否是障碍物。如果是障碍物，跳过。否则，计算新的糖果数：如果该格子的值>=0，则新的糖果数是当前糖果数加上该值；否则，新的糖果数是当前糖果数（比如，遇到-3或-2的情况）。新的步数是当前步数+1。
• 然后，检查该新坐标是否已经被访问过：
• 如果从未被访问过（即步数为无穷大），则更新该位置的糖果数和步数，并将该节点入队。
• 如果已经被访问过，但新步数比之前的步数更小，则更新糖果数和步数，并重新入队，因为更短的路径可能带来不同的糖果数。
• 如果新步数等于之前的步数，但新的糖果数比之前的更大，则更新糖果数为较大的值，并重新入队，因为同一时间步数下可能有更大的糖果数。

现在，具体步骤：

1. 读取输入，解析N，然后读取N行，每行N个数值，构成二维数组grid。
2. 找到妈妈的位置（-3）和宝宝的位置（-2），记录为start和end。
3. 如果start或end不存在，或者start等于end，或者无法到达（障碍物阻挡等情况），则返回-1。
4. 创建一个二维数组visited，每个元素保存到达该位置时的最大糖果数和步数。初始时，所有位置的steps为Infinity，candies为-1。start位置的steps为0，candies为0。
5. 使用队列进行BFS。初始时，将start的位置入队，记录candies为0，steps为0。
6. 对于队列中的每个节点，处理四个方向：
   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. 否则，不处理。
7. 当处理到end的位置时，记录当前的candies，但继续处理队列中的其他可能路径，因为可能存在同一时间步数下的更高糖果数。
8. 最终，如果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;
}

正确解答：

输入一行数不对的情况：

妈妈根本无法到达孩子的情况：

代码逐行解读：

1. 引入Node.js的readline模块，用于从标准输入（通常是键盘）读取数据。

const readline = require('readline');

2. 创建一个readline接口实例rl，配置其输入和输出分别为标准输入和标准输出。

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

3. 声明变量N（将用于存储网格的大小），grid（一个空数组，将用于存储网格的行），以及lineCount（用于跟踪已读取的行数）。

let N, grid = [], lineCount = 0;

4. 为rl接口注册一个’line’事件监听器，每当从标准输入读取一行时都会触发。

rl.on('line', (line) => {

5. 如果N未定义（即第一次读取行时），则将其设置为当前行的整数值（网格的大小）。否则，执行else分支。

  if (!N) {
    N = parseInt(line);
  } else {

6. 去除行的首尾空格，然后按空格分割成字符串数组，并使用map(Number)将每个字符串转换为数字，得到网格的一行。

    const row = line.trim().split(' ').map(Number);

7. 检查当前行的长度是否与网格的大小N相等。如果不等，打印-1并退出程序。

    if (row.length !== N) {
      console.error(-1);
      process.exit(1);
    }

8. 将当前行添加到grid数组中，并增加lineCount。

    grid.push(row);
    lineCount++;

9. 如果已读取的行数等于网格的大小N，则关闭rl接口并调用processInput函数来处理输入数据。

    if (lineCount === N) {
      rl.close();
      processInput();
    }
  }
});

10. 定义processInput函数，用于处理输入数据。

function processInput () {

11. 声明变量mom和baby，将用于存储起点（妈妈的位置）和终点（宝宝的位置）。

  let mom, baby;

12. 遍历grid数组的每一行和每个单元格。保存mom和baby的坐标。

  grid.forEach((row, i) => {
    row.forEach((val, j) => {
      if (val === -3) mom = [i, j];
      if (val === -2) baby = [i, j];
    });
  });

13. 调用bfs函数，传入起点和终点坐标，并打印返回的结果。

  console.log(bfs(mom, baby));
}

14. 定义bfs函数，实现广度优先搜索算法。声明一个方向数组dirs，包含四个方向（上、下、左、右）的坐标变化量。

function bfs (start, end) {
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];

15. 解构起点坐标，初始化一个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;

16. 将起点标记为已访问。

  visited[startX][startY] = true;

17. 当队列不为空时，执行循环。

  while (queue.length) {

18. 从队列中取出一个单元格和其路径上的糖果数。

    const [x, y, candies] = queue.shift();

19. 如果当前单元格是终点，则更新max为当前路径上的糖果数和max中的较大值，并继续下一次循环。

    if (x === endX && y === endY) {
      max = Math.max(max, candies);
      continue;
    }

20. 遍历四个方向。

    for (const [dx, dy] of dirs) {

21. 计算相邻单元格的坐标。

      const nx = x + dx;
      const ny = y + dy;

22. 检查相邻单元格是否在网格范围内、是否未访问过、并且不是障碍物（-1表示障碍物）。

      if (nx >= 0 && nx < N && ny >= 0 && ny < N
        && !visited[nx][ny]
        && grid[nx][ny] !== -1) {

23. 将相邻单元格标记为已访问，并将其添加到队列中，同时更新路径上的糖果数。

        visited[nx][ny] = true;
        queue.push([nx, ny, candies + Math.max(0, grid[nx][ny])]);
      }
    }
  }

24. 如果找到了到达终点的路径，则返回最大糖果数；否则返回-1。

  return max !== -Infinity ? max : -1;
}