# Dungeon Game

## Knight on the Unique Paths II

Same problem as Unique Paths II. Only different is to walk from end to start.

The Dungeon

```
+-----+-----+-----+
| -2 | -3 | 3 | A
+-----+-----+-----+
| -5 | -10 | 1 | B
+-----+-----+-----+
| 10 | 30 | -5 | C
+-----+-----+-----+
1 2 3
```

### The minimum health when the Knight reach the final Boss

Let make a table.

final room need `1 - (-5) = 6`

HP (`hp - 5 = 1`

to survive)

```
+-----+-----+-----+
| | | | A
+-----+-----+-----+
| | | | B
+-----+-----+-----+
| | | 6 | C
+-----+-----+-----+
1 2 3
```

the Knight can enter the final room from either `C2`

or `B3`

.

in `C2`

he can got `30`

HP, so if he could reach `C2`

then he can enter the final room. So he only need to survive (`1 HP`

).
`1 + 30 > 6`

.

in `B3`

he will get `1`

HP. the Knight will need `5 (6 - 1)`

HP to reach the final room.

```
+-----+-----+-----+
| | | | A
+-----+-----+-----+
| | | 5 | B
+-----+-----+-----+
| | 1 | 6 | C
+-----+-----+-----+
1 2 3
```

in `B2`

, the Knigth need `11 (1 - (-10))`

HP to reach `C2`

and `15 (5 - (-10)) to reach`

B3`.

If I were the Knight i would enter `C2`

because it requires less HP. `B2 = MIN(11, 15)`

```
+-----+-----+-----+
| | | | A
+-----+-----+-----+
| | 11 | 5 | B
+-----+-----+-----+
| | 1 | 6 | C
+-----+-----+-----+
1 2 3
```

In gerneral, HPNeed[x][y] = MIN(HPNeed[x + 1][y] - D[x][y], HPNeed[x][y + 1] - D[x][y]).

Sometimes, the HPNeed[x][y] might go below zero, like `C2`

<- `C3`

, that means `1 HP`

is OK.

The work is to fill up the table, and the first cell is the answer.

```
+-----+-----+-----+
| 7 | 5 | 2 | A
+-----+-----+-----+
| 6 | 11 | 5 | B
+-----+-----+-----+
| 1 | 1 | 6 | C
+-----+-----+-----+
1 2 3
```

### Source code *Read on Github*

```
1 public class Solution {
2
3 int minHealthReach(int hp, int room){
4 hp -= room;
5 if(hp <= 0){
6 return 1;
7 }
8
9 return hp;
10 }
11
12 public int calculateMinimumHP(int[][] dungeon) {
13
14 final int mx = dungeon.length;
15 final int my = dungeon[0].length;
16
17 dungeon[mx - 1][my - 1] = minHealthReach(1, dungeon[mx - 1][my - 1]);
18
19 for(int i = mx - 2; i >= 0; i--){
20 dungeon[i][my - 1] = minHealthReach(dungeon[i + 1][my - 1], dungeon[i][my - 1]);
21 }
22
23 for(int j = my - 2; j >= 0; j--){
24 dungeon[mx - 1][j] = minHealthReach(dungeon[mx - 1][j + 1], dungeon[mx - 1][j]);
25 }
26
27
28 for(int i = mx - 2; i >= 0; i--){
29 for(int j = my - 2; j >= 0; j--){
30 dungeon[i][j] = minHealthReach(Math.min(dungeon[i + 1][j], dungeon[i][j + 1]), dungeon[i][j]);
31 }
32 }
33
34 return dungeon[0][0];
35
36 }
37 }
```