Dungeon game solution


  • 0

    Reverse thinking[Accepted]
    This method is very simple.From the lower right corner of the princess to the upper left.Can only move left and up.
    Calculate the amount of blood needed to get to each square. The calculation method is
    dungeon[i][j]+=max(dungeon[i][j+1],dungeon[i+1][j]); (i+1<M,j+1<N)
    dungeon[i][j]+=dungeon[i+1][j]; (i+1<M,j+1>N)
    dungeon[i][j]+=dungeon[i][j+1]; (i+1>M,j+1<N)
    dungeon[i][j]=dungeon[i][j]; (i+1>M,j+1>N)
    The dungeon[0][0] value represents the knight's health value.So dungeon[0][0] takes negative value plus one as result.

    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            for(int i=dungeon.size()-1;i>=0;i--)
                for(int j=dungeon[i].size()-1;j>=0;j--)
                {
                    if(j+1<dungeon[i].size()&&i+1<dungeon.size())
                        dungeon[i][j]+=max(dungeon[i][j+1],dungeon[i+1][j]);
                    else if(j+1>=dungeon[i].size()&&i+1<dungeon.size())
                        dungeon[i][j]+=dungeon[i+1][j];
                    else if(j+1<dungeon[i].size()&&i+1>=dungeon.size())
                        dungeon[i][j]+=dungeon[i][j+1];
                    if(dungeon[i][j]>0)
                        dungeon[i][j]=0;
                }
                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.