# Dungeon game solution

• 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;
}
};
``````

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