class Solution {
public:
    int calculateMinimumHP(vector< vector<int> >& dungeon) {
        if(dungeon.size() == 0) return 0;

        int n = dungeon.size(), m = dungeon[0].size();
        vector< vector<int> > dp(n, vector<int>(m, INT_MAX));

        if(dungeon[n-1][m-1] < 0){
            dp[n-1][m-1] = -dungeon[n-1][m-1] + 1;
        }else{
            dp[n-1][m-1] = 1;

        }
        for(int i = n-1; i > -1; i--){
            for (int j = m-1; j > -1; j--){
                if(j-1>=0)
                if (dungeon[i][j-1] > 0){
                    if (dp[i][j] <= dungeon[i][j-1]){
                        dp[i][j-1] = 1;
                    }else{
                        dp[i][j-1] = min(dp[i][j-1], - dungeon[i][j-1] + dp[i][j]);
                    }
                }else{
                    dp[i][j-1] = min(dp[i][j-1], dp[i][j] - dungeon[i][j-1]);
                }

                if(i-1>=0)
                if (dungeon[i-1][j] > 0){
                    if (dp[i][j] <= dungeon[i-1][j]){
                        dp[i-1][j] = 1;
                    }else{
                        dp[i-1][j] = min(dp[i-1][j], - dungeon[i-1][j] + dp[i][j]);
                    }
                }else{
                    dp[i-1][j] = min(dp[i-1][j], dp[i][j] - dungeon[i-1][j]);
                }
            }
        }

        return dp[0][0];
    }
};