（相关搜索：最大值）（相关搜索：最大值）

Question

覆水难收
题目
在一块 n×n 的平地上，第 i 行，第 j 列的单元格中有 a i,j 个僵尸。计算鸭计划选定一个单元格并在其中放置一个炸弹，已知，炸弹有两种类型:

第一种类型的炸弹：十字架炸弹，引爆炸弹后，其放置炸弹的单元格的上、右、下、左四个方向的 m 个单元格将同放置炸弹的单元格一同销毁。

第二种类型的炸弹：对角线炸弹，引爆炸弹后，其放置炸弹的单元格的左上、左下、右上、右下四个方向的 m 个单元格将同放置炸弹的单元格一同销毁。

现在，给出平地上所有单元格中的僵尸数量，请你帮助计算鸭选择一个单元格和一种炸弹类型，使得引爆后炸死的僵尸数量最多。求出炸死僵尸数量的最大值。

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以采用动态规划的方法。我们将创建一个二维数组 dp，其中 dp[i][j] 存储的是在 (i, j) 单元格放置炸弹后可能消灭的最大僵尸数量。我们需要考虑两种炸弹类型，并且要注意边界情况。

首先，初始化 dp 数组，使其等于给定的僵尸数量矩阵。然后，我们遍历整个矩阵，对于每个位置 (i, j)，分别计算放置十字架炸弹和对角线炸弹的最大消灭僵尸数，取两者中的较大值更新到 dp[i][j]。

下面是完整的 C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int N = 50;
int n, m;
vector<vector<int>> grid(N, vector<int>(N));
vector<vector<int>> dp(N, vector<int>(N));

// 计算放置十字架炸弹后消灭的僵尸数
int crossBomb(int i, int j) {
    int zombies = 0;
    for (int di = -m; di <= m; di++) {
        for (int dj = -m; dj <= m; dj++) {
            if ((di == 0 && dj == 0) || di + dj > 0 || di + dj < 0) continue;
            int ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < n && nj >= 0 && nj < n)
                zombies += grid[ni][nj];
        }
    }
    return zombies;
}

// 计算放置对角线炸弹后消灭的僵尸数
int diagonalBomb(int i, int j) {
    int zombies = 0;
    for (int di = -m; di <= m; di++) {
        for (int dj = -m; dj <= m; dj++) {
            if ((di == 0 && dj == 0) || di != dj) continue;
            int ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < n && nj >= 0 && nj < n)
                zombies += grid[ni][nj];
        }
    }
    return zombies;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
            dp[i][j] = grid[i][j]; // 初始化 dp 矩阵
        }
    }

    // 动态规划计算最大消灭僵尸数
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = max(dp[i][j], crossBomb(i, j)); // 更新十字架炸弹的最大值
            dp[i][j] = max(dp[i][j], diagonalBomb(i, j)); // 更新对角线炸弹的最大值
        }
    }

    int maxZombies = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            maxZombies = max(maxZombies, dp[i][j]);
        }
    }

    cout << maxZombies << endl;
    return 0;
}

这段代码首先读入输入数据，然后初始化 dp 数组。接着，通过两层循环遍历整个矩阵，计算每个位置放置不同类型的炸弹后可能消灭的最大僵尸数量，并更新 dp 数组。最后，再次遍历 dp 数组找到最大值作为最终答案。