华为OD机试C卷-- 亲子游戏(Java & JS & Python & C)

华为OD机试C卷-- 亲子游戏(Java & JS & Python & C)

码农世界 2024-06-14 后端 135 次浏览 0个评论

获取题库不需要订阅专栏,可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。
题目描述
宝宝和妈妈参加亲子游戏,在一个二维矩阵(N*N)的格子地图上,宝宝和妈妈抽签决定各自的位置,地图上每个格子有不同的糖果数量,部分格子有障碍物。
游戏规则是妈妈必须在最短的时间(每个单位时间只能走一步)到达宝宝的位置,路上的所有糖果都可以拿走,不能走障碍物的格子,只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果(优先考虑最短时间到达的情况下尽可能多拿糖果)。

输入描述
第一行输入为 N,N 表示二维矩阵的大小
之后 N 行,每行有 N 个值,表格矩阵每个位置的值,其中:

  • -3:妈妈
  • -2:宝宝
  • -1:障碍
  • ≥0:糖果数(0表示没有糖果,但是可以走)

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

备注
地图最大 50*50

题目解析
这道题属于搜索类问题,可以通过广度优先搜索(BFS)来解决。因为要考虑到在最短时间内到达,同时收集最多的糖果,所以我们可以使用一个队列来保存当前状态,包括当前位置、已花费的时间和已经收集到的糖果数。每次从队列中取出一个状态,遍历其上下左右四个方

转载请注明来自码农世界,本文标题:《华为OD机试C卷-- 亲子游戏(Java & JS & Python & C)》

百度分享代码,如果开启HTTPS请参考李洋个人博客
每一天,每一秒,你所做的决定都会改变你的人生!

发表评论

快捷回复:

评论列表 (暂无评论,135人围观)参与讨论

还没有评论,来说两句吧...

Top