AlgoMooc
← 返回题库

X3022. 小慕的冒险游戏

困难通过率 58% · 提交 12 · 通过 7
DFS动态规划贪心

小慕正在开发一款冒险类游戏,玩家需要在地图上寻找食物并尽可能多地收集食物,同时要留意当前所在的位置,因为不同位置之间可以通过相互连接,这会影响最终获得的食物总量。 游戏开始时,小慕需要选择一个方格作为起点。每个方格上最多有 2 个传送门,通过这些传送门可以将玩家传送到指定的其他方格。每个方格上都标注了三个数字:id 、 和 value 。其中,id 表示方格的编号,parent-id 表示能够通过传送门到达该方格的方格编号,value 表示在该方格获得或失去的食物单位数。 玩家需要在地图中移动,每到达一个方格就获取或失去对应的食物单位数,直到满足退出条件之一。玩家的最终得分是所获得食物单位数的总和,目标是尽可能高。 地图设计时保证了玩家不可能两次到达同一个方格。因此,如果玩家当前所在的方格没有传送门,游戏会立即结束。此外,玩家在任何方格上都可以主动选择退出游戏,游戏也会结束。 请计算小慕退出游戏后,最多可以获得多少单位的食物。

提示:带虚线的词点一下有通俗解释。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。