Dungeon Game
The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon is represented by an m x n integer matrix dungeon, where the knight starts in the top-left corner and must reach the princess in the bottom-right corner.
The knight can move only:
- Right, or
- Down
Each cell affects the knight's health:
- A negative value means the knight loses health.
- A positive value means the knight gains health.
- Zero means the cell has no effect.
The knight dies immediately if his health drops to 0 or below at any point. Return the knight's minimum initial health required so that he can rescue the princess.
Example 1
-2 -3 3 -5 -10 1 10 30 -5
Input
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]Output
7Starting with 7 health allows the knight to follow a path where his health never drops to 0 or below.
Example 2
0
Input
dungeon = [[0]]Output
1The only cell has no effect, so the knight needs at least 1 initial health to stay alive.
Constraints
- m == dungeon.length
- n == dungeon[i].length
- 1 <= m, n <= 200
- -1000 <= dungeon[i][j] <= 1000