174 - Dungeon Game

Dungeon Game

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.

-2 (K)    -3        3
-5        -10       1
10        30      -5 (P)

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.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

Hide Tags

Dynamic Programming Binary Search

Hide Similar Problems

(M) Unique Paths (M) Minimum Path Sum

典型DP。
既然是要到达终点还活着，那就从终点往前推算。
终点如果是正的，到达之前至少需要一滴血，
若是负的，就得要保证加上这个负的还剩一滴血，那就是至少有 1 - （该负数）滴血。
这样就得到了到达终点之前的两个点必须有多少滴血了，然后以此类推，即可一路走到起点。

对于其他的点，不在边上的，应该从右边和下边的两个点里选择最小的，减去自己的，即为到达是至少要有的血数
注意计算的结果如果是小于 1 的，就应该直接写上 1，不然就挂啦。
在边上的，可以假想边的外面有个 INT_MAX，跟同一边边上的后一个之间求最小（也就是直接取同一边的后面一个）
这样就可以把代码统一了。

另外好奇 hint 里有个二分查找，难道是要每次选一个 mid，代入到矩阵里，dfs 算一次到达剩余的血有多少吗。。。？
试过一下，退出的条件不能直接写到达P的时候剩余 1 或者 1-dungeon[sz-1][zz-1] （例如 [[0,5],[-2,-3]]），没有深究。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        if(!dungeon.size() || !dungeon[0].size())
            return 0;
           
        return dp(dungeon, dungeon.size(), dungeon[0].size());
    }

    int dp(vector<vector<int>>& mtx, int sz, int zz)
    {
        for(int ii=sz-1; ii>=0; ii--)
        {
            for(int jj=zz-1; jj>=0; jj--)
            {
                int atleast = 1;
                if(sz-1>ii || zz-1>jj)
                    atleast = min((sz-1>ii)?mtx[ii+1][jj]:INT_MAX, (zz-1>jj)?mtx[ii][jj+1]:INT_MAX);
               
                mtx[ii][jj] =  max(1, atleast - mtx[ii][jj]);
            }
        }
        return mtx[0][0];       
    }
};
16 ms.