<p>The demons had captured the princess and imprisoned her in <strong>the bottom-right corner</strong> of a <code>dungeon</code>. The <code>dungeon</code> consists of <code>m x n</code> rooms laid out in a 2D grid. Our valiant knight was initially positioned in <strong>the top-left room</strong> and must fight his way through <code>dungeon</code> to rescue the princess.</p>

<p>The knight has an initial health point represented by a positive integer. If at any point his health point drops to <code>0</code> or below, he dies immediately.</p>

<p>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&#39;s health (represented by positive integers).</p>

<p>To reach the princess as quickly as possible, the knight decides to move only <strong>rightward</strong> or <strong>downward</strong> in each step.</p>

<p>Return <em>the knight&#39;s minimum initial health so that he can rescue the princess</em>.</p>

<p><strong>Note</strong> 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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-&gt; RIGHT -&gt; DOWN -&gt; DOWN.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> dungeon = [[0]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == dungeon.length</code></li>
	<li><code>n == dungeon[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>-1000 &lt;= dungeon[i][j] &lt;= 1000</code></li>
</ul>

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        n, m = len(dungeon), len(dungeon[0])
        storage = [[1 for _ in range(m)] for _ in range(n)]
        storage[-1][-1] = min(dungeon[-1][-1], 0)
        stack = [(n - 1, m - 1)]
        def get_dependency(a, b):
            res = []
            if a + 1 < n:
                res.append((a + 1, b))
            if b + 1 < m:
                res.append((a, b + 1))
            return res
        def is_ready(a, b):
            if a + 1 < n and storage[a + 1][b] == 1:
                return False
            if b + 1 < m and storage[a][b + 1] == 1:
                return False
            return True
        def get_next(a, b):
            res = []
            if a - 1 >= 0 and is_ready(a - 1, b):
                res.append((a - 1, b))
            if b - 1 >= 0 and is_ready(a, b - 1):
                res.append((a, b - 1))
            return res
        while stack:
            cur = stack[-1]
            stack = stack[:-1]
            candidates = get_next(*cur)
            for cand in candidates:
                a, b = cand
                dependencies = get_dependency(a, b)
                smallest_damage = -1 * 10 ** 9
                for dep in dependencies:
                    c, d = dep
                    smallest_damage = max(storage[c][d], smallest_damage)
                    if storage[c][d] > smallest_damage:
                        smallest_damage = storage[c][d]
                cand_damage = min(smallest_damage, 0) + dungeon[a][b]
                storage[a][b] = min(cand_damage, 0)
                stack.append(cand)
        print(storage)
        return 1 + storage[0][0] * -1
18100