|
2 | 2 |
|
3 | 3 | importcom.fishercoder.common.utils.CommonUtils; |
4 | 4 |
|
5 | | -/** |
6 | | - * 174. Dungeon Game |
7 | | -
|
8 | | - 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. |
9 | | -
|
10 | | - 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. |
11 | | -
|
12 | | - 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). |
13 | | -
|
14 | | - In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. |
15 | | -
|
16 | | - Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. |
17 | | -
|
18 | | - 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. |
19 | | - -2 (K) -3 3 |
20 | | - -5 -10 1 |
21 | | - 10 30 -5 (P) |
22 | | -
|
23 | | - Note: |
24 | | -
|
25 | | - The knight's health has no upper bound. |
26 | | - 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. |
27 | | -
|
28 | | - */ |
29 | 5 | publicclass_174 { |
30 | 6 |
|
31 | | -publicstaticclassSolution1 { |
32 | | -/** This problem should fill the dp matrix from bottom right. */ |
33 | | -publicintcalculateMinimumHP(int[][]dungeon) { |
34 | | -if (dungeon ==null ||dungeon.length ==0) { |
35 | | -return0; |
36 | | - } |
37 | | - |
38 | | -intheight =dungeon.length; |
39 | | -intwidth =dungeon[0].length; |
40 | | -int[][]dp =newint[height][width]; |
41 | | -dp[height -1][width -1] = |
42 | | - (dungeon[height -1][width -1] >0) ?1 :1 -dungeon[height -1][width -1]; |
43 | | - |
44 | | -//fill the last column |
45 | | -for (inti =height -2;i >=0;i--) { |
46 | | -inttemp =dp[i +1][width -1] -dungeon[i][width -1]; |
47 | | -dp[i][width -1] =Math.max(1,temp); |
48 | | - } |
49 | | - |
50 | | -//fill the last row |
51 | | -for (intj =width -2;j >=0;j--) { |
52 | | -inttemp =dp[height -1][j +1] -dungeon[height -1][j]; |
53 | | -dp[height -1][j] =Math.max(temp,1); |
54 | | - } |
55 | | - |
56 | | -for (inti =height -2;i >=0;i--) { |
57 | | -for (intj =width -2;j >=0;j--) { |
58 | | -intdown =Math.max(1,dp[i +1][j] -dungeon[i][j]); |
59 | | -intright =Math.max(1,dp[i][j +1] -dungeon[i][j]); |
60 | | -dp[i][j] =Math.min(down,right); |
| 7 | +publicstaticclassSolution1 { |
| 8 | +/** |
| 9 | + * This problem should fill the dp matrix from bottom right. |
| 10 | + */ |
| 11 | +publicintcalculateMinimumHP(int[][]dungeon) { |
| 12 | +if (dungeon ==null ||dungeon.length ==0) { |
| 13 | +return0; |
| 14 | + } |
| 15 | + |
| 16 | +intheight =dungeon.length; |
| 17 | +intwidth =dungeon[0].length; |
| 18 | +int[][]dp =newint[height][width]; |
| 19 | +dp[height -1][width -1] = |
| 20 | + (dungeon[height -1][width -1] >0) ?1 :1 -dungeon[height -1][width -1]; |
| 21 | + |
| 22 | +//fill the last column |
| 23 | +for (inti =height -2;i >=0;i--) { |
| 24 | +inttemp =dp[i +1][width -1] -dungeon[i][width -1]; |
| 25 | +dp[i][width -1] =Math.max(1,temp); |
| 26 | + } |
| 27 | + |
| 28 | +//fill the last row |
| 29 | +for (intj =width -2;j >=0;j--) { |
| 30 | +inttemp =dp[height -1][j +1] -dungeon[height -1][j]; |
| 31 | +dp[height -1][j] =Math.max(temp,1); |
| 32 | + } |
| 33 | + |
| 34 | +for (inti =height -2;i >=0;i--) { |
| 35 | +for (intj =width -2;j >=0;j--) { |
| 36 | +intdown =Math.max(1,dp[i +1][j] -dungeon[i][j]); |
| 37 | +intright =Math.max(1,dp[i][j +1] -dungeon[i][j]); |
| 38 | +dp[i][j] =Math.min(down,right); |
| 39 | + } |
| 40 | + } |
| 41 | + |
| 42 | +CommonUtils.printMatrix(dp); |
| 43 | +returndp[0][0]; |
61 | 44 | } |
62 | | - } |
63 | | - |
64 | | -CommonUtils.printMatrix(dp); |
65 | | -returndp[0][0]; |
66 | 45 | } |
67 | | - } |
68 | 46 | } |