龙与地下城游戏问题

龙与地下城游戏问题

题目描述

给定一个二维数组map，含义是一张地图，例如，如下矩阵
$$\left\{\begin{array}{ccc}-2& -3& 3\\ -5& -10& 1\\ 0& 30& -5\end{array}\right\}$$
游戏的规则如下:
1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?

根据map,输出初始血量。

输入描述：

第一行两个正整数n，m $\left(1\le n,m\le 10^3\right)$，接下来n行，每行m个整数，代表$ma{p}_{ij}$ $\left(-10^3\le ma{p}_{ij}\le 10^3\right)$。

输出描述：

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

示例1

输入

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

输出

7

示例2

输入

2 2
1 1
1 1

输出

1

备注：

时间复杂度 $O(n\ast m)$ ,额外空间复杂度 $O(min(n,m))$ 。

---

题解：

明显的二维 dp ，记状态表示为 F[i, j]，含义是：骑士走到 (i,j) ，并从该位置走到右下角应该具备的最低血量。此题比较有趣的地方是：如果我们选择 自顶向下 的方式，即从左上角出发，在前进过程中，每一个位置的最小血量是由后面的路径决定的，因此，自顶向下 方法是不行的，那么我们可以选择 自底向上 的方式，从右下角出发。

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int g[N][N];
int f[N][N];
int n, m;

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            scanf("%d", g[i] + j);
    }
    f[n - 1][m - 1] = g[n - 1][m - 1] < 0 ? -g[n - 1][m - 1] + 1 : 1;
    for (int j = m - 2; j >= 0; --j)
        f[n - 1][j] = max(f[n - 1][j + 1] - g[n - 1][j], 1);
    for (int i = n - 2; i >= 0; --i) {
        f[i][m - 1] = max(f[i + 1][m - 1] - g[i][m - 1], 1);
        for (int j = m - 2; j >= 0; --j) {
            int right = max(f[i][j + 1] - g[i][j], 1);
            int down = max(f[i + 1][j] - g[i][j], 1);
            f[i][j] = min(right, down);
        }
    }
    printf("%d\n", f[0][0]);
    return 0;
}

滚动数组优化

可以发现，直接去掉二维数组第一维即可，代码如下：

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int g[N][N];
int f[N];
int n, m;

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            scanf("%d", g[i] + j);
    }
    f[m - 1] = g[n - 1][m - 1] < 0 ? -g[n - 1][m - 1] + 1 : 1;
    for (int j = m - 2; j >= 0; --j)
        f[j] = max(f[j + 1] - g[n - 1][j], 1);
    for (int i = n - 2; i >= 0; --i) {
        f[m - 1] = max(f[m - 1] - g[i][m - 1], 1);
        for (int j = m - 2; j >= 0; --j) {
            int right = max(f[j + 1] - g[i][j], 1);
            int down = max(f[j] - g[i][j], 1);
            f[j] = min(right, down);
        }
    }
    printf("%d\n", f[0]);
    return 0;
}

本文地址：https://blog.csdn.net/MIC10086/article/details/108564933