-
Notifications
You must be signed in to change notification settings - Fork 38
Expand file tree
/
Copy pathSolution.java
More file actions
44 lines (41 loc) · 1.59 KB
/
Copy pathSolution.java
File metadata and controls
44 lines (41 loc) · 1.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Time : O() ; Space: O()
* @tag : Dynamic Programming; Binary Search
* @by : Steven Cooks
* @date: Aug 4, 2015
***************************************************************************
* Description:
*
* 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.
*
* 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.
*
***************************************************************************
* {@link }
*/
package _174_DungeonGame;
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
return 0;
}
}