注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex174 Dungeon Game  

2015-05-31 17:09:44|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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)-33
-5-101
1030-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.

题目很长,但是归纳起来就是动态规划。就是每点的生民值不能少于1,在到达某一点之后。从后往前递推,开一个二维数组dp[i][j],表示到达(i,j)所需的最小生命力。

 在中间的时候有两种走法,一个right,一个是down
 如果是往right走 
           right = myMax(dp[i][j + 1] - dungeon[i][j], 1);
 如果是往down走
           down = myMax(dp[i + 1][j] - dungeon[i][j], 1);
 首先初始化dp[m-1][n-1] 如果他是负数,则需要1-dungeon[m-1][n-1]的生命力
                        如果是正数,则只需要1
 然后初始化最后一列和最后一行,然后网上递推,到了最后的时候,就是需要的最小生命力
 见代码

/*
* 动态规划的算法,从后往前递推
* 在中间的时候有两种走法,一个right,一个是down
* 开一个二维数组 dp[i][j],表示从上一个状态到达这里需要的最小权值
* 如果是往right走
right = myMax(dp[i][j + 1] - dungeon[i][j], 1);
* 如果是往down走
down = myMax(dp[i + 1][j] - dungeon[i][j], 1);
* 首先初始化dp[m-1][n-1] 如果他是负数,则需要1-dungeon[m-1][n-1]的生命力
* 如果是正数,则只需要1
* 然后初始化最后一列和最后一行,然后网上递推,到了最后的时候,就是需要的
* 最小生命力
*/
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.size() <= 0 || dungeon[0].size() <= 0)
return 0;

int result;
result = minimum(dungeon);
return result;
}
int minimum(vector<vector<int>>& dungeon)
{
int m = dungeon.size();
int n = dungeon[0].size();
vector<vector<int>>dp(m,vector<int>(n,0)); //开一个二维数组,表示上一个状态到达i,j所需的最小权值
if (dungeon[m - 1][n - 1] >= 0)
dp[m - 1][n - 1] = 1;
else
dp[m - 1][n - 1] = 1-dungeon[m - 1][n - 1];
int i = 0,j=0;
for (i = m - 2; i >= 0; i--)
dp[i][n - 1] = myMax(dp[i+1][n - 1] - dungeon[i][n - 1],1);
for (j = n - 2; j >= 0; j--)
dp[m-1][j] = myMax(dp[m-1][j+1] - dungeon[m-1][j], 1);
int right, down;
for (i = m - 2; i >= 0; i--)
{
for (j = n - 2; j >= 0; j--)
{
down = myMax(dp[i + 1][j] - dungeon[i][j], 1);
right = myMax(dp[i][j + 1] - dungeon[i][j], 1);
dp[i][j] = myMin(down,right);
}
}

return dp[0][0];

}
int myMin(int a, int b)
{
return a > b ? b : a;
}
int myMax(int a, int b)
{
return a > b ? a : b;
}
};


  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017