LeetCode174—Dungeon Game

浅浅的花香味﹌ 2022-07-14 15:17 109阅读 0赞

## 原题 ##

[原题链接][Link 1]

> The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
> 
> The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
> 
> Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).
> 
> In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
> 
> Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.
> 
> For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

> Notes:
> 
> The knight’s health has no upper bound.  
> Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

--------------------

## 分析 ##

题目很有意思，就是在M×N地图上，骑士有N点血，在初始位置(0,0)处，而皇后在(M−1,N−1)的位置，现在地图中每个方格位置(i,j) 都要么能给骑士补血，要么骑士需要扣血，当骑士的血降到小于或等于0，则骑士立刻死亡。问骑士如果要就得皇后，初始状态下至少需要多少血？

骑士向右或者向下走，如果血量小于0就死掉了，这会使得计算变得很复杂。如果我们从后往前看，从最后一个格子逆推回去，就会简单很多。

首先假设dp(i,j)为骑士在(i,j)处的最小血量，那么下个状态，骑士有两个选择：往右，往下。

由于我们是从后往前推，所以现在我们已经知道dp(i\+1,j)和dp(i,j\+1)。

**举个例子：**  
以dp(i\+1,j)为例，假设骑士往下走：  
则dungeon(i,j)表示骑士在(i,j)处扣掉的血量或者是补充的血量。

为了完成由(i,j)−>(i\+1,j)的状态转移，则必须满足式子：  
dp(i,j)\+dungeon(i,j)≥dp(i\+1,j),dp(i,j)>0

即：  
dp(i,j)≥dp(i\+1,j)−dungeon(i,j),dp(i,j)>0

要求最小血量，且dp(i,j)必须大于0，因此得出最终的式子：  
dp(i,j)=max\{ 1,dp(i\+1,j)−dungeon(i,j)\}

上述式子只考虑一个方向，如果要考虑两个方向，则需考虑取两者较小的值，综合起来得到：  
dp(i,j)=min\{ max\{ 1,dp(i\+1,j)−dungeon(i,j)\},max\{ 1,dp(i,j\+1)−dungeon(i,j)\}\}(1)

根据(1)式写代码就简单了。

### **代码** ###

#include <iostream>
    #include <vector>
    #include <string>
    #include <iterator>
    #include <algorithm>
    using namespace std;
    
    
    class Solution {
        public:
        int calculateMinimumHP(vector<vector<int> >& dungeon) {
            int M = dungeon.size();//row
            int N = dungeon[0].size();//col
            vector<string>path;
            vector< vector<int> >dp(M,vector<int>(N));    
            dp[M-1][N-1]=max(1-dungeon[M-1][N-1],1);
            //last row
            for(int col = N-2;col>=0;--col)
            {
                dp[M-1][col]=max(1,dp[M-1][col+1]-dungeon[M-1][col]);
            }
            //last col
            for(int row = M-2;row>=0;--row)
            {
                dp[row][N-1]=max(1,dp[row+1][N-1]-dungeon[row][N-1]);
            }
            for(int i= M-2;i>=0;--i)
            {
                for(int j=N-2;j>=0;--j)
                {
                    int down=max(1,dp[i+1][j]-dungeon[i][j]);
                    int right=max(1,dp[i][j+1]-dungeon[i][j]);
                    dp[i][j]=min(down,right);
                    if(down<right)
                    {
                        path.push_back("down");
                    }
                    else
                    {
                        path.push_back("right");
                    }
                }
            }
            ostream_iterator<string> output_it(cout);
            adjacent_difference(path.rbegin(),path.rend(),ostream_iterator<string>(cout),
                [](string x,string y)->string{
       cout<<"->";return x;});//打印路径
            cout<<endl;
            return dp[0][0];
        }
    };

[Link 1]: https://leetcode.com/problems/dungeon-game/