华为OD统一考试 - 亲子游戏
题目描述
宝宝和妈妈参加亲子游戏,在一个二维矩阵(N*N)的格子地图上,宝宝和妈妈抽签决定各自的位置,地图上每个格子有不同的糖果数量,部分格子有障碍物。
游戏规则是妈妈必须在最短的时间(每个单位时间只能走一步)到达宝宝的位置,路上的所有糖果都可以拿走,不能走障碍物的格子,只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果(优先考虑最短时间到达的情况下尽可能多拿糖果)。
输入描述
第一行输入为 N,N 表示二维矩阵的大小
之后 N 行,每行有 N 个值,表格矩阵每个位置的值,其中:
- -3:妈妈
- -2:宝宝
- -1:障碍
- ≥0:糖果数(0表示没有糖果,但是可以走)
输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果,行末无多余空格
备注
地图最大 50*50
用例
输入 | 4 3 2 1 -3 1 -1 1 1 1 1 -1 2 -2 1 2 3 |
输出 | 9 |
说明 | 此地图有两条最短路径可到达宝宝位置,绿色线和黄色线都是最短路径6步,但黄色拿到的糖果更多,9个。 |
输入 | 4 3 2 1 -3 -1 -1 1 1 1 1 -1 2 -2 1 -1 3 |
输出 | -1 |
说明 | 此地图妈妈无法到达宝宝位置 |
题目解析
本题需要我们优先找到妈妈到宝宝的最短路径,如果存在多条最短路径的话,则选择其中能拿到最多糖果数的路径。
那么如何求解妈妈到宝宝的最短路径呢?
其实很简单,就是单纯的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)") }
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。