|
| 1 | +packagehard; |
| 2 | + |
| 3 | +importutils.CommonUtils; |
| 4 | + |
| 5 | +/**174. Dungeon Game |
| 6 | +
|
| 7 | + Total Accepted: 27313 |
| 8 | + Total Submissions: 125827 |
| 9 | + Difficulty: Hard |
| 10 | +
|
| 11 | +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. |
| 12 | +
|
| 13 | +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. |
| 14 | +
|
| 15 | +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). |
| 16 | +
|
| 17 | +In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. |
| 18 | +
|
| 19 | +Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. |
| 20 | +
|
| 21 | +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. |
| 22 | +-2 (K) -3 3 |
| 23 | +-5 -10 1 |
| 24 | +10 30 -5 (P) |
| 25 | +
|
| 26 | +Notes: |
| 27 | +
|
| 28 | + The knight's health has no upper bound. |
| 29 | + 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. |
| 30 | +
|
| 31 | +Credits: |
| 32 | +Special thanks to @stellari for adding this problem and creating all test cases.*/ |
| 33 | +publicclassDungeonGame { |
| 34 | + |
| 35 | +/**This problem should fill the dp matrix from bottom right.*/ |
| 36 | +publicintcalculateMinimumHP(int[][]dungeon) { |
| 37 | +if(dungeon ==null ||dungeon.length ==0)return0; |
| 38 | + |
| 39 | +intheight =dungeon.length,width =dungeon[0].length; |
| 40 | +int[][]dp =newint[height][width]; |
| 41 | +dp[height-1][width-1] = (dungeon[height-1][width-1] >0) ?1 :1-dungeon[height-1][width-1]; |
| 42 | + |
| 43 | +//fill the last column |
| 44 | +for(inti =height-2;i >=0;i--){ |
| 45 | +inttemp =dp[i+1][width-1] -dungeon[i][width-1]; |
| 46 | +dp[i][width-1] =Math.max(1,temp); |
| 47 | + } |
| 48 | + |
| 49 | +//fill the last row |
| 50 | +for(intj =width-2;j >=0;j--){ |
| 51 | +inttemp =dp[height-1][j+1] -dungeon[height-1][j]; |
| 52 | +dp[height-1][j] =Math.max(temp,1); |
| 53 | + } |
| 54 | + |
| 55 | +for(inti =height-2;i >=0;i--){ |
| 56 | +for(intj =width -2;j >=0;j--){ |
| 57 | +intdown =Math.max(1,dp[i+1][j] -dungeon[i][j]); |
| 58 | +intright =Math.max(1,dp[i][j+1] -dungeon[i][j]); |
| 59 | +dp[i][j] =Math.min(down,right); |
| 60 | + } |
| 61 | + } |
| 62 | + |
| 63 | +CommonUtils.printMatrix(dp); |
| 64 | +returndp[0][0]; |
| 65 | + } |
| 66 | + |
| 67 | + |
| 68 | +publicstaticvoidmain(String...strings){ |
| 69 | +DungeonGametest =newDungeonGame(); |
| 70 | +// int[][] dungeon = new int[1][1]; |
| 71 | +// dungeon[0][0] = 0; |
| 72 | + |
| 73 | +// int[][] dungeon = new int[1][1]; |
| 74 | +// dungeon[0][0] = -200; |
| 75 | + |
| 76 | +// int[][] dungeon = new int[1][2]; |
| 77 | +// dungeon[0][0] = 0; |
| 78 | +// dungeon[0][1] = -3; |
| 79 | + |
| 80 | +// int[][] dungeon = new int[2][1]; |
| 81 | +// dungeon[0][0] = -3; |
| 82 | +// dungeon[1][0] = -7; |
| 83 | + |
| 84 | +int[][]dungeon =newint[2][1]; |
| 85 | +dungeon[0][0] =2; |
| 86 | +dungeon[1][0] =1; |
| 87 | + |
| 88 | +// int[][] dungeon = new int[1][2]; |
| 89 | +// dungeon[0][0] = -3; |
| 90 | +// dungeon[0][1] = 5; |
| 91 | + |
| 92 | +// int[][] dungeon = new int[2][2]; |
| 93 | +// dungeon[0][0] = 2; |
| 94 | +// dungeon[0][1] = 1; |
| 95 | +// dungeon[1][0] = 1; |
| 96 | +// dungeon[1][1] = -1; |
| 97 | + |
| 98 | +// int[][] dungeon = new int[1][2]; |
| 99 | +// dungeon[0][0] = 0; |
| 100 | +// dungeon[0][1] = 0; |
| 101 | + |
| 102 | +// int[][] dungeon = new int[2][1]; |
| 103 | +// dungeon[0][0] = 0; |
| 104 | +// dungeon[1][0] = 0; |
| 105 | + |
| 106 | +// int[][] dungeon = new int[3][3]; |
| 107 | +// dungeon[0][0] = -2; |
| 108 | +// dungeon[0][1] = -3; |
| 109 | +// dungeon[0][2] = 3; |
| 110 | +// dungeon[1][0] = -5; |
| 111 | +// dungeon[1][1] = -10; |
| 112 | +// dungeon[1][2] = 1; |
| 113 | +// dungeon[2][0] = 10; |
| 114 | +// dungeon[2][1] = 30; |
| 115 | +// dungeon[2][2] = -5; |
| 116 | + |
| 117 | +// int[][] dungeon = new int[2][3]; |
| 118 | +// dungeon[0][0] = 0; |
| 119 | +// dungeon[0][1] = 0; |
| 120 | +// dungeon[0][2] = 0; |
| 121 | +// dungeon[1][0] = 1; |
| 122 | +// dungeon[1][1] = 1; |
| 123 | +// dungeon[1][2] = -1; |
| 124 | +CommonUtils.printMatrix(dungeon); |
| 125 | +System.out.println(test.calculateMinimumHP(dungeon)); |
| 126 | + } |
| 127 | + |
| 128 | +publicintcalculateMinimumHP_attemp2_failed(int[][]dungeon) { |
| 129 | +if(dungeon ==null ||dungeon.length ==0)return0; |
| 130 | + |
| 131 | +intheight =dungeon.length,width =dungeon[0].length; |
| 132 | +int[][]dp =newint[height][width]; |
| 133 | +dp[0][0] =dungeon[0][0] >0 ?1 :1-dungeon[0][0]; |
| 134 | + |
| 135 | +//fill the first column |
| 136 | +for(inti =1;i <height;i++){ |
| 137 | +dp[i][0] =dungeon[i][0] >=0 ?dp[i-1][0] : -dungeon[i][0]+dp[i-1][0]; |
| 138 | + } |
| 139 | + |
| 140 | +//fill the first row |
| 141 | +for(intj =1;j <width;j++){ |
| 142 | +dp[0][j] =dungeon[0][j] >=0 ?dp[0][j-1] : -dungeon[0][j]+dp[0][j-1]; |
| 143 | + } |
| 144 | + |
| 145 | +for(inti =1;i <height;i++){ |
| 146 | +for(intj =1;j <width;j++){ |
| 147 | +dp[i][j] =dungeon[i][j] >=0 ?Math.min(dp[i][j-1],dp[i-1][j]) : -dungeon[i][j]+Math.min(dp[i][j-1],dp[i-1][j]); |
| 148 | + } |
| 149 | + } |
| 150 | + |
| 151 | +CommonUtils.printMatrix(dp); |
| 152 | +returndp[height-1][width-1]; |
| 153 | + } |
| 154 | +} |