技术学习分享_一航技术 技术资讯 #yyds干货盘点# 动态规划专题:龙与地下城游戏问题

#yyds干货盘点# 动态规划专题:龙与地下城游戏问题

广告位

1.简述:

描述

给定一个二维数组map,含义是一张地图,例如,如下矩阵

#yyds干货盘点# 动态规划专题:龙与地下城游戏问题

游戏的规则如下:1)骑士从左上角出发,每次只能向右或向下走,最后到达右下角见到公主。2)地图中每个位置的值代表骑士要遭遇的事情。如果是负数,说明此处有怪兽,要让骑士损失血量。如果是非负数,代表此处有血瓶,能让骑士回血。3)骑士从左上角到右下角的过程中,走到任何一个位置时,血量都不能少于1。为了保证骑土能见到公主,初始血量至少是多少?

根据map,输出初始血量。

输入描述:

第一行两个正整数n,m  #yyds干货盘点# 动态规划专题:龙与地下城游戏问题,接下来n行,每行m个整数,代表#yyds干货盘点# 动态规划专题:龙与地下城游戏问题

输出描述:

输出一个整数,表示答案。

示例1

输入:

3 3
-2 -3 3
-5 -10 1
0 30 -5

输出:

7

示例2

输入:

2 2
1 1
1 1

输出:

1

2.代码实现:

import java.util.*;
public class Main{
public static void main(String []args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int [][]map=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
map[i][j]=input.nextInt();
}
}
int [][]dp=new int[n][m];
// 用hpMatrix表示骑士从任意一格到达终点所需要的最少血量
dp[n-1][m-1]=(map[n-1][m-1]>0?1:-map[n-1][m-1]+1);
for(int j=m-2;j>=0;j--){
if(map[n-1][j]-dp[n-1][j+1]>=0){
dp[n-1][j]=1;
}
else{
dp[n-1][j]=dp[n-1][j+1]-map[n-1][j];
}
}
for(int i=n-2;i>=0;i--){
if(map[i][m-1]-dp[i+1][m-1]>=0){
dp[i][m-1]=1;
}
else{
dp[i][m-1]=dp[i+1][m-1]-map[i][m-1];
}
}
for(int i=n-2;i>=0;i--){
for(int j=m-2;j>=0;j--){
int minNeed=Math.min(dp[i+1][j],dp[i][j+1]); //两个方向最少需要的血
if(map[i][j]-minNeed>=0){ //同样的思路,如果够用,那就只需要1点血进来,因为最少一点血
dp[i][j]=1;
}
else{
dp[i][j]=minNeed-map[i][j]; //如果不够用的话,就只能增加进来时候的血
}
}
}
System.out.println(dp[0][0]);
}
}

本文来自网络,不代表技术学习分享_一航技术立场,转载请注明出处。

作者: 一航技术

上一篇
下一篇
广告位

发表回复

返回顶部