文档章节

174. Dungeon Game

Do0M
 Do0M
发布于 2017/08/26 21:35
字数 765
阅读 2
收藏 0
点赞 0
评论 0

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.
一道普通的动态规划题,迷宫中有BUFF也有DEBUFF,当血量降到0就挂了。从左上角出发,只能向下或向右走,终点在右下角,求怎么走需要的初始血量最少。
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];
}
可以从终点往起点倒推,对迷宫里(除终点外)每一个点计算 从这个点走到终点至少要扣掉多少血,推到起点也就得到结果了。因为从下往上从右往左一行一行遍历,所以每一个点的右和下都在之前算过,因此可以知道下一步是走→好还是走↓好(比如一个值是-5,一个是-2,当然是-2好了,因为-2意味着走这一步之前血量剩下3就可以走到终点而不挂)。知道了下一步怎么走就可以计算当前这个点的数值了:如果下一步是个正数,意味着只要当前角色的血量大于1,就能走到终点而不挂,那就不用改当前点的数值了(如果这一步是BUFF,反正死不了改不改都一样;如果是DEBUFF,那就更不能改,后面能不能活至少要先过了这一步再说,比方这一步有个-10的debuff,下一步是5,角色任然需要11的血量才能走过这一步,因此不改);如果下一步是个负数,那么要在当前数值(也就是BUFF或者DEBUFF的数值)上加上这个负数,意味着从这个点走到终点,至少还要扣掉这么多血。
总之一通DP就阔以了。

这题是HARD,正确率23%,leetcode里算难题了。

本文转载自:http://blog.csdn.net/limk96/article/details/72902741

共有 人打赏支持
Do0M
粉丝 0
博文 8
码字总数 24
作品 0
leetcode 174. Dungeon Game 完美世界秋招编程题2

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

努力的C
2017/10/02
0
0
经典游戏开源再现

经典的游戏总是难以忘怀,当年的游戏制作公司或许现已不在,但是其中的幸运儿却可以通过开源的方式再度重现。 这里列举了几款经典游戏的开源克隆: Command & Conquer: Red Alert 红色警戒:...

老枪
2011/06/04
4.5K
8
[oj.leetcode] #174 - Dungeon Game 一次特别的DP之旅

原题篇幅挺长,关于一个2D关卡游戏,这里以矩阵的方式简单陈述一下。 在一个二维数组M*N中, 有一个王子需要从起点[0][0]出发,移动到终点[m-1][n-1],每次移动一格,方向只能向右或者向下。出...

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

终于,做完了kuangbin大神带你飞的专题一之简单搜索,实在有一股无法言喻的感觉,每道题类型都差不多但细节实现却有点细微区别,所以14道题我就只当作5题了。。 棋盘问题 稍微变了点形的皇后...

weixin_39637396
2017/12/13
0
0
python一课一练(测试单元)

承接上一课在windows下建立一个固定结构的工程所建立的文件结构,这一课我讲一下如何对python工程进行测试。

fantasiter
2016/12/20
4
0
spark shell 运行异常

Association with remote system [akka.tcp://sparkMaster@master :7077] has failed, address is now gated for [5000] ms. Reason: [Association failed with [akka.tcp://sparkMaster@mas......

sca7
2016/08/26
408
2
地下城生成器--Dungeon Generator

Dungeon Generator提供一个不同值的二维矩阵可用于创建一个地下城游戏并生成地下城的GIF图像。 在脚本使用的图像用来代表实际的地牢,在游戏中,二维矩阵将被使用,而且矩阵中不同的值将会被...

匿名
2016/09/12
489
0
SGU题目列表(按照AC人数排序)

15509 100 A+B 05909 102 Coprimes 05424 105 Div 3 05024 123 The sum 03552 115 Calendar 03365 135 Drawing Lines 03235 184 Patties 03103 107 987654321 problem 03019 113 Nearly prim......

m2012
2012/04/29
0
0
ChaosEsque Anthology 14 发布

ChaosEsque Anthology 14 发布,此版本添加了新的自由 dungeon DarkHold 区域;改进了 monster 代码;改进了 stonation 和 paralyse 功能;各种 bug 修复和改进。 ChaosEsque Anthology 是一...

oschina
2014/01/18
486
0
【iOS-Cocos2d游戏开发之二】Cocos2D 游戏开发资源贴(教程以及源码)

这两天抽出一些时间学习cocos2d,发现资料N多,而且讲解的相当的全面;那么这段时间我也处于不断的学习中,当然好东西不私藏,这里我把比较经典的一个iOS游戏开发书籍给出,当然很多童鞋,我...

junwong
2012/03/02
6.2K
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

ndarray花式索引

花式索引 花式索引(Fancy indexing)是一个NumPy术语,它指的是利用整数数组进行索引。假设我们有一个8×4数组: In [117]: arr = np.empty((8, 4))In [118]: for i in range(8): ....

火力全開
2分钟前
0
0
Mybaties报错Error querying database

Mybaties我们经常用到动态SQL,如下我们利用动态去做判断,这样写当然没问题,但是当我们不是去判断orgCode(本文中orgCode一直为String类型)是否为空而是判断orgCode是否是一个值的时候该怎...

王子城
4分钟前
0
0
Android 调用手机自带的下载器下载

亲测有用,原文下载地址: 原文地址:https://blog.csdn.net/weixin_36554045/article/details/79108796 下面是原文: 创建一个广播类 public class UpdataBroadcastReceiver extends Broad...

她叫我小渝
7分钟前
0
0
idea工具debug断点红色变成灰色,断点无效

来自:idea工具debug断点红色变成灰色 没事别瞎点,禁用了断点当然不走了 看这篇博客底下的评论笑死我了 真香警告!

不开心的时候不要学习
10分钟前
0
0
知识点总结

jq如何拿到data-info的自定义属性 1.1 原生可以获取到所有属性el.attrbutes 1.2 jq的$(el).attr('属性名称') 继承的几种方式,原型链 2.1 扩展原型对象实现继承 2.2 替换原型对象实现继承 2....

litCabbage
12分钟前
0
0
python语言规范

http://zh-google-styleguide.readthedocs.io/en/latest/google-python-styleguide/python_style_rules/...

ghou-靠墙哭
16分钟前
0
0
istio 监控,遥测 (理论)

Istio提供了一种灵活的模型来强制执行授权策略并收集网格中服务的遥测。 基础架构后端旨在提供用于构建服务的支持功能。它们包括诸如访问控制系统,遥测捕获系统,配额执行系统,计费系统等之...

xiaomin0322
18分钟前
0
0
阿里资深专家面试问题收集

corejava hashcode相等的两个对象一定相等吗?equals呢?反过来相等吗? 介绍一下集合框架? hashtable,hashmap底层实现是什么?hashtable和concurrenthashmap底层实现的区别? hashmap和treemap的...

undefine
19分钟前
8
0
alpine安装软件指定安装源

linux-alpine安装软件指定安装源 一、永久修改apk下载源地址 vi etc/apk/repositories 替换成阿里源 http://mirrors.aliyun.com/alpine/v3.8/main/http://mirrors.aliyun.com/alpine/v3...

我心中有猛狗
20分钟前
0
0
Centos7通过yum安装nginx

添加源地址(直接install可能不是最新版本的) sudo rpm -Uvh http://nginx.org/packages/centos/7/noarch/RPMS/nginx-release-centos-7-0.el7.ngx.noarch.rpm 安装 sudo yum install -y ng......

iplusx
22分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部