The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN
.
-2 (K) | -3 | 3 |
-5 | -10 | 1 |
10 | 30 | -5 (P) |
public class Solution { public int calculateMinimumHP(int[][] dungeon) { if (dungeon == null || dungeon.length == 0 || dungeon[0] == null || dungeon[0].length == 0) { return 1; } int row = dungeon.length; int col = dungeon[0].length; int[][] dp = new int[row--][col--]; dp[row][col] = dungeon[row][col] > 0 ? 1 : -dungeon[row][col] + 1; for (int i = col-1; i >= 0; i--) { dp[row][i] = Math.max(dp[row][i+1] - dungeon[row][i], 1); } int right = 0; int down = 0; for (int i = row - 1; i >= 0; i--) { dp[i][col] = Math.max(dp[i+1][col] - dungeon[i][col], 1); for (int j = col-1; j >= 0; j--) { right = Math.max(dp[i][j+1] - dungeon[i][j], 1); down = Math.max(dp[i+1][j] - dungeon[i][j], 1); dp[i][j] = Math.min(right, down); } } return dp[0][0]; } }
相关推荐
Unity地下城资源包
一款PYTHON地下城小游戏,使用pygame库制作,希望有用。
地牢游戏
地牢游戏要将游戏导入 intellij,请使用此链接。请确保使用 INTELLIJ PLSSSSSSSSS 它已内置 VCS 控制 BTW #要做的事情1)。 确保气泡的移动速度永远不会低于某个速度 2)。 修复从墙壁上反弹的问题 3)。...
Anatolia MUD是一款基于Diku MUD的多用户地下城游戏。 安那托利亚(Anatolia)是小亚细亚的另一个名字:亚洲与欧洲相交。 Anatolia MUD是一款基于文本的多用户游戏。 有关更多详细信息,请访问:...
JXFire是基于Java游戏服务器框架Project RedDwarf的用Java编写的多用户地下城游戏。
像素地牢游戏 一个基于2D数组的基本地牢游戏,具有非常基本的像素艺术/动画。 作为DIG 3480的最终项目-计算机作为媒介。 在4天内创建。 最初要求游戏具有一个级别,但是此实现的独特之处在于,每次用户玩游戏时,...
地牢游戏 基于文本的游戏,玩家可以在导致不同结局的随机选择事件的不同路径之间进行选择。 每个播放过程都是唯一的; 同一位玩家在不同的游戏流程中可能会经历非常不同的经历,从击败每个怪物到逃离地牢,到将骷髅...
##地牢游戏Dungeon Game 是一个用 Java 编写的 Dungeon Crawler Prototype。 ######Getting Started Extract latest.zip 运行 Dungeon-Game.jar ####特征随机生成的地图存货基本战斗系统####截图
Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of 1 Bits Gray ...
lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-旋转阵列,198-房屋强盗 二分法 153-在旋转排序数组(II)中查找最小值,162-查找峰值元素 结构 ...174-Dungeon Game, HARD: 188
你知道龙与地下城吗,如果知道你会愿意参与这个项目,在它的基础上建立一个小游戏,一种基于DnD 3.5规则的MUD(多用户地牢)风格。 视频会议和音频可能会输入以帮助游戏。
去地牢Concordia制作Game Game Jam时制作的Go Go Dungeon存储库。 您可以使用npm run dev运行开发服务器。
Get to know techniques and approaches to procedurally generate game content in C++ using Simple and Fast ... Procedural Dungeon Generation Chapter 10. Component-Based Architecture Chapter 11. Epilogue
Make a 2D RPG in a Weekend shows you how to create your very own dungeon crawler game in RPG Maker VX Ace in a single weekend. The entire process, from start to finish, is covered within this book. ...
YAD是“还有另一个地下城游戏”。 它支持任何可以作为插件编写的用户界面。
#Legacy Dungeon Legacy Dungeon是具有随机生成的地图的自上而下的2D地牢爬虫。随着我们从使用Javax.swing库渲染图形到使用Lightweight Java Game Library(LWJGL)的转变,该游戏的开发过程目前仍处于暂停状态。 在...
在每个新标签页上都包含Android和iOS手机游戏Dungeon Boss的高清图片! 在每个新标签页上都包含Android和iOS手机游戏Dungeon Boss的高清图片! 我们始终会更新图像,因此请随时检查...我们将为您提供5星评级! 如果...
具有多人游戏的Unity引擎中最暗的Dungeon端口。 几乎与原始游戏完全相同。 所有音频和图形资产都将被忽略!项目状态实施: 物业管理 所有英雄/怪物 所有战斗效果/状态 地牢/任务生成 城镇事件 库存,所有物品,古玩 ...