华为OD统一考试 - 亲子游戏

题目描述

宝宝和妈妈参加亲子游戏，在一个二维矩阵（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，来判断是否处于新层

import Foundation
func ODTest_2_64() {
    print("输入描述")
    print("第一行输入为 N，N 表示二维矩阵的大小")
    var n = Int(readLine() ?? "") ?? 0
    print("之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：-3：妈妈-2：宝宝-1：障碍≥0：糖果数（0表示没有糖果，但是可以走）")

    var matrix: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
    for i in 0 ..< n {
        matrix[i] = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    }
    print("输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格")
    var candy = Array(repeating: Array(repeating: -1, count: n), count: n)
    var queue: [Int] = []

    for i in 0 ..< n {
        for j in 0 ..< n {
            candy[i][j] = -1
            if matrix[i][j] == -3 {
                candy[i][j] = 0
                queue.append(i * n + j) // 二维坐标一维化
            }
        }
    }

    // 记录题解
    var ans = -1

    let offsets = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    // bfs 按层扩散
    while !queue.isEmpty {
        // 记录当前扩散层的点
        var newQueue: [Int] = []

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

        for pos in queue {
            // 源点坐标
            let x = pos / n
            let y = pos % n

            // 向四个方向扩散
            for offset in offsets {
                // 当前扩散点坐标
                let newX = x + offset[0]
                let 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.append(newX * n + 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
    }

    print("\(ans)")
}