华为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