Repository navigation
Expand file tree
/
Copy pathdungeonGame.cpp
More file actions
88 lines (77 loc) · 3.52 KB
/
Copy pathdungeonGame.cpp
File metadata and controls
88 lines (77 loc) · 3.52 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Source : https://oj.leetcode.com/problems/dungeon-game/
// Author : Hao Chen
// Date : 2015-01-16
/**********************************************************************************
*
* 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.
*
* Credits:Special thanks to @stellari for adding this problem and creating all test cases.
*
**********************************************************************************/
class Solution {
public:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int row = dungeon.size();
int col = row>0 ? dungeon[0].size() : 0;
if (row<=0 || col <=0) return 0;
//dp[r][c] = min( max( dp[r+1][c] - dungeon[r][c], 1), max( dp[r][c+1] - dungeon[r][c], 1) );
int dp[row][col];
memset(dp, 0, sizeof(dp));
for(int r=row-1; r>=0; r--){
for (int c=col-1; c>=0; c--){
/*if (r == row - 1 && c == col - 1 ){
dp[r][c] = max(1 - dungeon[r][c], 1);
}else if ( r == row - 1 ) {
dp[r][c] = max(dp[r][c+1] - dungeon[r][c], 1);
}else if ( c == col - 1 ) {
dp[r][c] = max(dp[r+1][c] - dungeon[r][c], 1);
}else{
dp[r][c] = min( max( dp[r+1][c] - dungeon[r][c], 1), max( dp[r][c+1] - dungeon[r][c], 1) );
}*/
if (r == row - 1 && c == col - 1 ){
dp[r][c] = max(1 - dungeon[r][c], 1);
}else{
int h1 = ( c == col-1 ) ? INT_MAX : max(dp[r][c+1] - dungeon[r][c], 1);
int h2 = ( r == row-1 ) ? INT_MAX : max(dp[r+1][c] - dungeon[r][c], 1);
dp[r][c] = min( h1, h2 );
}
}
}
return dp[0][0];
}
};