龙与地下城游戏问题

龙与地下城游戏问题

题目描述

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

根据map,输出初始血量。

输入描述：

第一行两个正整数n，m ( 1 ≤ n , m ≤ 1 0 3 ) \left ( 1\leq n,m\leq 10^{3} \right ) (1≤n,m≤103)，接下来n行，每行m个整数，代表 m a p i j map_{ij} mapij​ ( − 1 0 3 ≤ m a p i j ≤ 1 0 3 ) \left( -10^3 \leq map_{ij} \leq 10^{3}\right ) (−103≤mapij​≤103)。

输出描述：

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

示例1

输入

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

输出

7

示例2

输入

2 2
1 1
1 1

输出

1

备注：

时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) ,额外空间复杂度 O ( m i n ( n , m ) ) O(min(n,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