我要招人

去企业版

首页 > 试题广场 >

龙与地下城游戏问题

[编程题]龙与地下城游戏问题

热度指数：5121 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

$\begin{Bmatrix} -2&-3&3 \\ -5&-10&1\\ 0&30&-5 \end{Bmatrix}$

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

根据map,输出初始血量。

输入描述:

第一行两个正整数n，m  ，接下来n行，每行m个整数，代表。

输出描述:

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

示例1

输入

输出

示例2

输入

2 2
1 1
1 1

输出

备注:

时间复杂度,额外空间复杂度

算法知识视频讲解

牛客418427545号

发表于 2022-05-13 15:05:41

逆推，当某一个位置少于1是，要取1 终点：dp[-1][-1]=max(1-nums[-1][-1],1) 最后1行： dp[m-1][i-1]=max(dp[m-1][i]-nums[m-1][i-1],1) 最后1列：dp[i-1][n-1]=max(dp[i][n- 展开全文

牛客74234309号

发表于 2022-03-11 19:20:18

从终点开始动态规划 import java.util.*; public class Main{ public static void main(String []args){ 展开全文

静寂旮旯

发表于 2022-04-24 13:07:09

解题思路：入坑思路：起点和终点搞反，即把坐标（n-1，m-1）作为最终解出口。发现问题在求解的过程中总是要回溯到从（0，0）点到当前位置所经过路径上的血瓶计算，感觉问题始终在搞清和没搞清之间，非常痛苦。正确思路：是从（n-1，m-1）点到（0，0）点的求解，在一路走的过程当中只需要考虑当前存展开全文

星晨

发表于 2020-11-16 22:59:25

典型的动态规划从左上角触发，每次向右或向下走，最后到达右下角，我们要求的是初始值的血 dp[i][j] 从arr[i][j] 位置到右下角最少需要多少血 dp[m-1][n-1] = arr[m-1][n-1] > 0 ? 1:-arr[m-1][n-1] +1 //能到达的下一个位置 -去展开全文

吱吱1111111

发表于 2024-04-16 04:36:04

应该是目前最最优的解，没想出来从起点推到终点的规划方法。如果能够从起点起推，那就可以用滚动数组存储输入数据，进一步优化内存。下面这篇解是从起点开始推的，能通过用例测试，但没有考虑极端情况，即最大收益路线和最低血量路线可能并不重合，可是他的解法里，每一步最低血量的决策跟随了最大收益。https://b 展开全文

w王晴q

发表于 2024-04-20 16:59:20

#include <cmath> #include <iostream> #include <vector> using namespace std; int main() { int a, b; while (cin >> a &g 展开全文

manderous

发表于 2024-10-11 11:11:15

import sys lines = [] for line in sys.stdin: a = line.split() lines.append(a) m = int(lines[0][1]) n = int(lines[0][0]) DP = [[0 for _ in ra 展开全文

牛客418427545号

发表于 2022-05-13 15:01:36

m,n=map(int,input().split()) nums=[] dp=[[0 for i in range(n)] for j in range(m)] for i in range(m): nums.append(list(map(int,input().split()))) dp[-1 展开全文

快支棱起来的椰子很愤怒

发表于 2022-01-18 15:51:08

n, m = map(int, input().split()) matrix = [] for _ in range(n): matrix.append(list(map(int, input().split()))) dp = [0] * m dp[-1] = 1 if matrix[- 展开全文

牛客357197674号

发表于 2022-08-26 11:12:43

while True: try: n, m = list(map(int, input().split() 展开全文

问题信息

动态规划穷举

上传者：小小

难度：

9条回答 100收藏 4943浏览

通过挑战的用户

查看代码

Asphyxiay

2022-09-15 00:53:45
牛客61729...

2022-09-14 11:04:45
Ljiong

2022-09-14 06:30:43
你真的不如他呢

2022-09-13 16:42:13
牛客14696...

2022-09-13 11:05:44

龙与地下城游戏问题

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题