龙与地下城游戏问题

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

热度指数：4679 时间限制：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

输出

备注:

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

算法知识视频讲解

Python 3

Kiron_L

def solution(nums, n, m):
    dp = [[0 for j in range(m)] for i in range(n)]
    dp[-1][-1] = max(1, 1 - nums[n - 1][-1])
    for i in range(2, n + 1):
        dp[-i][m - 1] = max(1, dp[-i + 1][m - 1] - nums[-i][m - 1])
    for j in range(2, m + 1):
        dp[n - 1][-j] = max(1, dp[n - 1][-j + 1] - nums[n - 1][-j])
    for i in range(2, n + 1):
        for j in range(2, m + 1):
            dp[-i][-j] = max(1, min(dp[-i + 1][-j], dp[-i][-j + 1]) - nums[-i][-j])
    return dp[0][0]


n, m = map(int, input().split())
nums = []
for i in range(n):
    nums.append(list(map(int, input().split())))
res = solution(nums, n, m)
print(res)

发表于 2022-08-17 22:00:55 回复(0)