最新华为OD机试真题-亲子游戏(200分)
大家好这里是清隆学长 ，一枚热爱算法的程序员
ACM金牌️团队 ｜ 编程一对一辅导
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
感谢大家的订阅➕ 和 喜欢 和手里的小花花
最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
在线评测链接
亲子游戏(200分)
评测功能需要 =>订阅专栏<= 后联系清隆解锁～
OJ题目截图
亲子游戏
问题描述
K小姐和她的孩子 LYA 参加了一个亲子游戏。游戏场地是一个 的二维矩阵地图。地图上的每个格子都有一定数量的糖果,或者是障碍物。游戏开始时,K小姐和 LYA 分别被随机分配到地图上的两个不同位置。
游戏规则是 K小姐必须在最短的时间内到达 LYA 所在的位置。每个单位时间,K小姐只能向上下左右相邻的格子移动一步。在移动的过程中,K小姐可以拿走经过格子上的所有糖果,但不能穿过障碍物的格子。
请计算在最短时间内到达 LYA 所在位置时,K小姐最多可以拿到多少糖果。
输入格式
第一行输入一个正整数 ,表示地图的大小。
接下来 行,每行包含 个整数,表示地图上每个格子的情况:
- 表示该格子是 K小姐的初始位置
- 表示该格子是 LYA 的位置
- 表示该格子是障碍物
- 非负整数表示该格子上的糖果数量
输出格式
输出一个整数,表示 K小姐在最短时间内到达 LYA 所在位置时,最多可以拿到的糖果数量。
样例输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
样例输出
9
样例解释
K小姐初始位置在 (0, 3),LYA 的位置在 (3, 0)。K小姐最短路径为 (0, 3) -> (1, 3) -> (2, 3) -> (3, 2) -> (3, 1) -> (3, 0),总共可以拿到 3 + 1 + 2 + 2 + 1 = 9 颗糖果。
数据范围
题解
我们可以使用广度优先搜索 (BFS) 来解决这个问题。我们从 K小姐的初始位置开始,将其加入队列。然后不断从队列中取出一个位置,并尝试向四个方向移动。如果移动后的位置是可以到达的,我们就将其加入队列,并更新该位置的最大糖果数量。
具体做法是,我们使用一个二维数组 来记录每个位置的最大糖果数量。初始时,除了 K小姐的初始位置之外,其他位置的糖果数量都是 。在搜索的过程中,如果一个位置是第一次被访问到,我们就将其加入队列,并将其糖果数量初始化为 。否则,我们就更新该位置的糖果数量,取当前位置糖果数和上一步位置的糖果数量之和的最大值。
当我们找到 LYA 的位置时,该位置的糖果数量就是 K小姐在最短时间内到达该位置时可以拿到的最多糖果数量。
参考代码
- Python
from collections import deque
def bfs(n, g, dx, dy):
q = deque([(i, j) for i in range(n) for j in range(n) if g[i][j] == -3])
w = [[0] * n for _ in range(n)]
for x, y in q:
w[x][y] = 0
while q:
x, y = q.popleft()
if g[x][y] == -2:
return w[x][y]
for i in range(4):
x1, y1 = x + dx[i], y + dy[i]
if 0 <= x1 < n and 0 <= y1 < n and g[x1][y1] != -1:
if w[x1][y1] == 0:
q.append((x1, y1))
w[x1][y1] = 0
w[x1][y1] = max(w[x1][y1], max(0, g[x1][y1]) + w[x][y])
return -1
if __name__ == '__main__':
n = int(input())
g = []
for _ in range(n):
g.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, 1,