174. Dungeon Game Hard

1/**
2 * [174] Dungeon Game
3 *
4 * The demons had captured the princess 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 was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.
5 * 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.
6 * Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).
7 * To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
8 * Return the knight's minimum initial health so that he can rescue the princess.
9 * Note that 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.
10 *  
11 * Example 1:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg" style="width: 253px; height: 253px;" />
13 * Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
14 * Output: 7
15 * Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.
16 * 
17 * Example 2:
18 * 
19 * Input: dungeon = [[0]]
20 * Output: 1
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	m == dungeon.length
26 * 	n == dungeon[i].length
27 * 	1 <= m, n <= 200
28 * 	-1000 <= dungeon[i][j] <= 1000
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/dungeon-game/
34// discuss: https://leetcode.com/problems/dungeon-game/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    pub fn calculate_minimum_hp(dungeon: Vec<Vec<i32>>) -> i32 {
40        0
41    }
42}
43
44// submission codes end
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn test_174() {
52    }
53}
54