The problem should state that "the Knight cannot enter the same room more than once"


  • 0
    X

    otherwise, in the example, if the knight has 5 initially and he can move right->right->down->up->down->down


  • 1
    K

    The problem states:

    In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.


  • 0
    X

    thanks


    sharing my solution

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

        for(int i=dungeon.size()-1;i>=0;i--){
            for(int j=dungeon[i].size()-1;j>=0;j--){
                if(i==dungeon.size()-1 && j==dungeon[i].size()-1){
                    dungeon[i][j]=min(0,dungeon[i][j]);
                    continue;
                }
                
                int accu=INT_MIN;
                if(i<dungeon.size()-1)
                accu=max(accu,min(0,dungeon[i+1][j]));
                if(j<dungeon[i].size()-1)
                accu=max(accu,min(0,dungeon[i][j+1]));
                
                dungeon[i][j]=min(0,accu+dungeon[i][j]);
            }
        }
        
        return -dungeon[0][0]+1;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.