(C卷,200分)- 亲子游戏（Java & JS & Python & C）

在线OJ刷题

题目描述

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

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

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

输入描述

第一行输入为 N，N 表示二维矩阵的大小

之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：

• -3：妈妈
• -2：宝宝
• -1：障碍
• ≥0：糖果数（0表示没有糖果，但是可以走）

输出描述

输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

备注

地图最大 50*50

用例

题目解析

本题需要我们优先找到妈妈到宝宝的最短路径，如果存在多条最短路径的话，则选择其中能拿到最多糖果数的路径。

那么如何求解妈妈到宝宝的最短路径呢？

其实很简单，就是单纯的BFS按层扩散，比如下图所示：

此时将妈妈位置作为源点，开始按层扩散

扩散到第一层

扩散第二层

扩散到第三层

扩散到第四层

扩散到第五层，此时扩散到了宝宝位置，也就是说妈妈到宝宝位置的最短距离是五步。

即扩散的层数，就是步数距离。

那么如何在扩散过程中，统计宝宝能获得的糖果数呢？

此时我们可以定义一个糖果矩阵，初始时糖果矩阵都为0

扩散到第一层

此时第一层上各点拿到的糖果数 = 扩散源点的糖果数 + 自身位置已有的糖果数

扩散到第二层

此时，我们发现，绿色框的点对应的糖果数很容易求解 = 扩散源点的糖果数 + 自身位置已有的糖果数。

但是红色框点，他可以被两个扩散源点同时扩散到，此时我们应该保留能带来较大糖果数的扩散源点的扩散结果

扩散到第三层

扩散到第四层

扩散到第五层时，宝宝位置只会被一个源点扩散到，即下图红框点，即此时宝宝在最短距离路径下，最多可获得24个糖果

并且，一旦BFS扩散层到达了宝宝所在位置，则等待此层扩散完，就可以停止BFS逻辑。

因为，继续扩散到后续层，虽然也可能到达宝宝位置，但是路径已经不是最短的了。

上面逻辑实现时，比较难的是：如何实现按层扩散？

此时我们可以借助candy矩阵，我们可以发现在上面扩散过程中，新的层的candy值都为0，因此当一个源点开始扩散，扩散到的新位置的candy值：

• 如果candy值为0的话，则说明当前点是新层的点，此时我们将该点加入到新层的BFS队列中
• 如果candy值不为0，则说明该点可能是新层，也可能是老层，此时我们只做更新该点candy值动作（可能会改掉老层点的candy值，但是不会有影响，因为一层套一层，老层点的candy值改变不会影响隔了一层得下一层点）

注意：本题输入矩阵中得各点糖果数可能为0，因此这里不能根据扩散点的candy值为0来确定当前扩散点是不是处于新层。

我们应该将candy矩阵各元素初始化为-1，然后扩散点根据candy值是否为-1，来判断是否处于新层

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());

  const candy = new Array(n).fill(0).map(() => new Array(n).fill(-1));

  let queue = [];

  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));

    for (let j = 0; j < n; j++) {
      // 妈妈的位置
      if (matrix[i][j] == -3) {
        candy[i][j] = 0;
        queue.push([i, j]);
      }
    }
  }

  // 记录题解
  let ans = -1;

  const offsets = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  // bfs 按层扩散
  while (queue.length > 0) {
    // 记录当前扩散层的点
    const newQueue = [];

    // 当前层是否有宝宝所在的点
    let flag = false;

    // 源点坐标
    for (let [x, y] of queue) {
      // 向四个方向扩散
      for (let [offsetX, offsetY] of offsets) {
        // 当前扩散点坐标
        const newX = x + offsetX;
        const newY = y + offsetY;

        // 当前扩散点坐标越界，或者扩散点是墙，则无法扩散
        if (
          newX < 0 ||
          newX >= n ||
          newY < 0 ||
          newY >= n ||
          matrix[newX][newY] == -1
        )
          continue;

        // 当前扩散点坐标对应的糖果数量为-1，说明对应扩散点坐标位置还没有加入到当前扩散层
        if (candy[newX][newY] == -1) {
          newQueue.push([newX, newY]); // 加入当前扩散层
        }

        // 当前扩散点可能会被多个源点扩散到，因此比较保留扩散过程中带来的较大糖果数
        // candy[newX][newY] 记录的是当前扩散点获得的糖果数
        // candy[x][y] + Math.max(0, matrix[newX][newY]) 记录的是从源点(x,y)带来的糖果数 + (newX,newY)位置原本的糖果数
        candy[newX][newY] = Math.max(
          candy[newX][newY],
          candy[x][y] + Math.max(0, matrix[newX][newY])
        );

        // 如果当前扩散点是宝宝位置，则可以停止后续层级的bfs扩散，因为已经找到宝宝的最短路径长度（即扩散层数）
        if (matrix[newX][newY] == -2) {
          ans = candy[newX][newY];
          flag = true;
        }
      }
    }

    // 已经找到去宝宝位置的最短路径和最大糖果数，则终止bfs
    if (flag) break;

    // 否则继续
    queue = newQueue;
  }

  console.log(ans);
})();

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  static int n;
  static int[][] matrix;
  static int[][] candy;
  static int[][] offsets = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();

    matrix = new int[n][n];
    candy = new int[n][n];

    LinkedList<Integer> queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        candy[i][j] = -1;

        matrix[i][j] = sc.nextInt();
        // 妈妈的位置
        if (matrix[i][j] == -3) {
          candy[i][j] = 0;
          queue.add(i * n + j); // 二维坐标一维化
        }
      }
    }

    // 记录题解
    int ans = -1;

    // bfs 按层扩散
    while (queue.size() > 0) {
      // 记录当前扩散层的点
      LinkedList<Integer> newQueue = new LinkedList<>();

      // 当前层是否有宝宝所在的点
      boolean flag = false;

      for (int pos : queue) {
        // 源点坐标
        int x = pos / n;
        int y = pos % n;

        // 向四个方向扩散
        for (int[] offset : offsets) {
          // 当前扩散点坐标
          int newX = x + offset[0];
          int newY = y + offset[1];

          // 当前扩散点坐标越界，或者扩散点是墙，则无法扩散
          if (newX < 0 || newX >= n || newY < 0 || newY >= n || matrix[newX][newY] == -1) continue;

          // 当前扩散点坐标对应的糖果数量为-1，说明对应扩散点坐标位置还没有加入到当前扩散层
          if (candy[newX][newY] == -1) {
            newQueue.addLast(newX * n + newY); // 加入当前扩散层
          }

          // 当前扩散点可能会被多个源点扩散到，因此比较保留扩散过程中带来的较大糖果数
          // candy[newX][newY] 记录的是当前扩散点获得的糖果数
          // candy[x][y] + Math.max(0, matrix[newX][newY]) 记录的是从源点(x,y)带来的糖果数 + (newX,newY)位置原本的糖果数
          candy[newX][newY] =
              Math.max(candy[newX][newY], candy[x][y] + Math.max(0, matrix[newX][newY]));

          // 如果当前扩散点是宝宝位置，则可以停止后续层级的bfs扩散，因为已经找到宝宝的最短路径长度（即扩散层数）
          if (matrix[newX][newY] == -2) {
            ans = candy[newX][newY];
            flag = true;
          }
        }
      }

      // 已经找到去宝宝位置的最短路径和最大糖果数，则终止bfs
      if (flag) break;

      // 否则继续
      queue = newQueue;
    }

    System.out.println(ans);
  }
}

Python算法源码

# 输入获取
n = int(input())

queue = []

candy = [[-1] * n for _ in range(n)]

matrix = []
for i in range(n):
    matrix.append(list(map(int, input().split())))

    for j in range(n):
        # 妈妈的位置
        if matrix[i][j] == -3:
            candy[i][j] = 0
            queue.append((i, j))

offsets = ((0, -1), (0, 1), (-1, 0), (1, 0))


# 算法入口
def bfs():
    global queue

    # 记录题解
    ans = -1

    # bfs 按层扩散
    while len(queue) > 0:
        # 记录当前扩散层的点
        newQueue = []

        # 当前层是否有宝宝所在的点
        flag = False

        # 源点坐标
        for x, y in queue:
            # 向四个方向扩散
            for offsetX, offsetY in offsets:
                # 当前扩散点坐标
                newX = x + offsetX
                newY = y + offsetY

                # 当前扩散点坐标越界，或者扩散点是墙，则无法扩散
                if newX < 0 or newX >= n or newY < 0 or newY >= n or matrix[newX][newY] == -1:
                    continue

                # 当前扩散点坐标对应的糖果数量为-1，说明对应扩散点坐标位置还没有加入到当前扩散层
                if candy[newX][newY] == -1:
                    newQueue.append((newX, newY))  # 加入当前扩散层

                # 当前扩散点可能会被多个源点扩散到，因此比较保留扩散过程中带来的较大糖果数
                # candy[newX][newY] 记录的是当前扩散点获得的糖果数
                # candy[x][y] + max(0, matrix[newX][newY]) 记录的是从源点(x,y)带来的糖果数 + (newX,newY)位置原本的糖果数
                candy[newX][newY] = max(candy[newX][newY], candy[x][y] + max(0, matrix[newX][newY]))

                # 如果当前扩散点是宝宝位置，则可以停止后续层级的bfs扩散，因为已经找到宝宝的最短路径长度（即扩散层数）
                if matrix[newX][newY] == -2:
                    ans = candy[newX][newY]
                    flag = True

        # 已经找到去宝宝位置的最短路径和最大糖果数，则终止bfs
        if flag:
            break

        # 否则继续
        queue = newQueue

    return ans


# 算法调用
print(bfs())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

int main() {
    int n;
    scanf("%d", &n);

    int matrix[n][n];
    int candy[n][n];

    LinkedList *queue = new_LinkedList();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            candy[i][j] = -1;

            scanf("%d", &matrix[i][j]);
            // 妈妈的位置
            if (matrix[i][j] == -3) {
                candy[i][j] = 0;
                addLast_LinkedList(queue, i * n + j); // 二维坐标一维化
            }
        }
    }

    int offsets[4][2] = {{-1, 0},
                         {1,  0},
                         {0,  -1},
                         {0,  1}};

    // 记录题解
    int ans = -1;

    // bfs 按层扩散
    while (queue->size > 0) {
        // 记录当前扩散层的点
        LinkedList *newQueue = new_LinkedList();

        // 当前层是否有宝宝所在的点
        int flag = 0;

        ListNode *cur = queue->head;
        while (cur != NULL) {
            // 源点坐标
            int x = cur->ele / n;
            int y = cur->ele % n;

            // 向四个方向扩散
            for (int i = 0; i < 4; i++) {
                // 当前扩散点坐标
                int newX = x + offsets[i][0];
                int newY = y + offsets[i][1];

                // 当前扩散点坐标越界，或者扩散点是墙，则无法扩散
                if (newX < 0 || newX >= n || newY < 0 || newY >= n || matrix[newX][newY] == -1) continue;

                // 当前扩散点坐标对应的糖果数量为-1，说明对应扩散点坐标位置还没有加入到当前扩散层
                if (candy[newX][newY] == -1) {
                    addLast_LinkedList(newQueue, newX * n + newY);
                }

                // 当前扩散点可能会被多个源点扩散到，因此比较保留扩散过程中带来的较大糖果数
                // candy[newX][newY] 记录的是当前扩散点获得的糖果数
                // candy[x][y] + remain 记录的是从源点(x,y)带来的糖果数 + (newX,newY)位置原本的糖果数
                int remain = MAX(0, matrix[newX][newY]);
                candy[newX][newY] = MAX(candy[newX][newY], candy[x][y] + remain);

                // 如果当前扩散点是宝宝位置，则可以停止后续层级的bfs扩散，因为已经找到宝宝的最短路径长度（即扩散层数）
                if (matrix[newX][newY] == -2) {
                    ans = candy[newX][newY];
                    flag = 1;
                }
            }

            cur = cur->next;
        }

        // 已经找到去宝宝位置的最短路径和最大糖果数，则终止bfs
        if (flag) break;

        // 否则继续
        queue = newQueue;
    }

    printf("%dn", ans);

    return 0;
}