package temworkingarea;
/**
* <pre>
* 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)
*
* Notes:
*
* The knight's health has no upper bound.
* Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
* </pre>
* */
public class DungeonGame {
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length;
int column = dungeon[0].length;
int[][] tem = new int[row][];
for (int i = 0; i < tem.length; i++) {
tem[i] = new int[column];
}
if (dungeon[row - 1][column - 1] >= 0) {
tem[row - 1][column - 1] = 1;
} else {
tem[row - 1][column - 1] = 1 - dungeon[row - 1][column - 1];
}
for (int i = row - 2; i >= 0; i--) {
tem[i][column - 1] = c(dungeon[i][column - 1],
tem[i + 1][column - 1]);
}
for (int j = column - 2; j >= 0; j--) {
tem[row - 1][j] = c(dungeon[row - 1][j], tem[row - 1][j + 1]);
}
for (int i = row - 2; i >= 0; i--) {
for (int j = column - 2; j >= 0; j--) {
tem[i][j] = Math.min(c(dungeon[i][j], tem[i + 1][j]),
c(dungeon[i][j], tem[i][j + 1]));
}
}
return tem[0][0];
}
private int c(int value, int preResult) {
if (value == 0)
return preResult;
if (value > 0) {
if (value >= preResult)
return 1;
return preResult - value;
}
return preResult - value;
}
}
}
分享到:
相关推荐
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
vs code LeetCode 插件
leetcode中文版
"candy.erl","dungeon_game.erl", "interleaving_string.erl","search_insert_position.erl", "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现...
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题
leetcode全套解答python版本。包括更新到10月份的的leetcode
LeetCode-Swift, 快速LeetCode解决方案 LeetCodeLeetCode在线判断是一个包含很多收费算法的网站。 them Google Google Google Google LinkedIn this this repo 。 请免费参考并收费STAR以支持这个 repo,