## 174. Dungeon Game 转

Do0M

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.

``````int calculateMinimumHP(int** dungeon, int dungeonRowSize, int dungeonColSize) {
for(int i=dungeonRowSize-1;i>=0;i--){
for(int j=dungeonColSize-1;j>=0;j--){
if(i==dungeonRowSize-1&&j==dungeonColSize-1){
continue;
}
else if(i==dungeonRowSize-1){
if(dungeon[i][j+1]<0){
dungeon[i][j]+=dungeon[i][j+1];
}
}
else if(j==dungeonColSize-1){
if(dungeon[i+1][j]<0){
dungeon[i][j]+=dungeon[i+1][j];
}
}
else{
int max=dungeon[i+1][j]>=dungeon[i][j+1]?dungeon[i+1][j]:dungeon[i][j+1];
if(max<0){
dungeon[i][j]+=max;
}
}
}
}
return dungeon[0][0]>=0?1:1-dungeon[0][0];
}``````

### Do0M

leetcode 174. Dungeon Game 完美世界秋招编程题2

2017年完美世界秋招的原题。 原题链接：https://leetcode.com/problems/dungeon-game/description/ 骑士救公主，每个格子可能加血也可能减血。而且到达每个格子时的血量必须大于等于1，问骑士...

2017/10/02
0
0
[oj.leetcode] #174 - Dungeon Game 一次特别的DP之旅

teaspring
2015/02/19
0
0
[kuangbin带你飞]专题一 简单搜索 (17/1000)

weixin_39637396
2017/12/13
0
0
【POJ - 2251】Dungeon Master （bfs+优先队列）

Dungeon Master Descriptions: You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with roc......

Sky丨Star
06/02
0
0
POJ 2251 Dungeon Master

Dungeon Master 　　You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It tak......

suvvm
2018/12/06
0
0

OSChina 周六乱弹 —— 如果是个帅小伙你愿意和他出去吗

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 小小编辑推荐：《Ghost 》游戏《死亡搁浅》原声 《Ghost 》游戏（《死亡搁浅》原声） - Au/Ra / Alan Walker 手机党少年们想听歌，请使劲儿戳...

53分钟前
93
5
java通过ServerSocket与Socket实现通信

Blueeeeeee

6
0

5
0

16
0

（手机横屏看源码更方便） 注：java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期，但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

19
0