import queue
from typing import List


class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # M and N are dimensions of the dungeon
        M = len(dungeon)
        N = len(dungeon[0])
        # create a dp matrix for dungeon
        dp = [[0]*N for _ in range(M)]
        # from right-bot to left-top
        for i in range(M-1, -1, -1):
            for j in range(N-1, -1, -1):
                if i == M-1 and j == N-1:
                    # at (M-1, N-1) you at least need 1 hp left
                    dp[M - 1][N - 1] = 1
                elif i == M-1 and j != N-1:
                    # at (M-1, j) you need at least 1 hp to be alive, and you need prepare at least
                    # dp[i][j+1] - dungeon[i][j+1] hp to go right cell
                    dp[M-1][j] = max(1, dp[i][j+1] - dungeon[i][j+1])
                elif i != M-1 and j == N-1:
                    # at (i, N-1) you need at least 1 hp to be alive, and you need prepare at least
                    # dp[i+1][j] - dungeon[i+1][j] hp to go bot cell
                    dp[i][j] = max(1, dp[i+1][j] - dungeon[i+1][j])
                else:
                    # at (i, j) upi need at least dp[i + 1][j] - dungeon[i + 1][j] hp to go bot cell and 
                    # dp[i][j+1] - dungeon[i][j+1] hp to go right cell. Also at cell (i, j) you need at least 1 hp.
                    dp[i][j] = max(1, min(dp[i + 1][j] - dungeon[i + 1][j], dp[i][j+1] - dungeon[i][j+1]))
        # you must go through (0, 0) cell, which is not calculated above.
        return max(1, dp[0][0] - dungeon[0][0])