B4263 [GESP202503 四级] 荒地开垦

· · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题是一道较复杂的考察二维数组的试题。

对于每个荒地格子，我们先数一数它上下左右四个方向中有多少个杂物邻居。如果一个荒地格子周围没有任何杂物邻居，就说明它在当前状态下可以直接开垦。我们把这样的格子数出来，记为 ori。

在这道题中，我们可以记录方向数组来简化“判断上下左右四个方向”的流程。具体而言，我们可以定义两个常量数组：

const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};

那么我们只需要使用一重循环（即下面参考代码中的 k 循环），即可访问当前坐标 (i,j) 的上下左右邻居，并且做对应的判断。

// 假设数组 d[i][j] 用于记录：与坐标 (i, j) 相邻的格子有多少个格子有杂物
for (________) {
    for (________) { 
        if (________) { // 枚举当前的坐标 (i, j)，如果是空地的话
            int bad = 0; // 周围有多少个杂物
            for (int k = 0; ________; k++) {
                int ni = i + di[k], nj = ________; // 获得上下左右位置的坐标 (ni, nj)
                if (________) // 如果 (ni, nj) 在方阵内，且这个位置上是杂物
                    ________;
            }
            ________;
            ________  // 如果周围没杂物，能直接开垦
        }
    }
}

接着，我们考虑清除一个格子的杂物会带来的变化。有的同学可能会编写一个二重循环先枚举网格图上要清理的杂物，再和上面的流程一样，在内部套一个二重循环去计算新图上的最多能够开垦的荒地块数。但是这样做的时间复杂度是 O(n^2m^2)，无法通过测试数据。因此，我们必须要想一个办法优化这个做法。

实际上，对于一个杂物格子，如果清除上面的杂物，会带来两个方面的变化：

因此我们可以将所有荒地格子中“恰好只有 1 个杂物邻居”的，找到是哪一个杂物格子挡住了它，把这个荒地格子对那个杂物格子的“贡献数”加 1。然后对每个杂物格子，计算它自己的贡献（如果周围没有别的杂物，就算 1）加上前面统计的“被它挡住的荒地数”，得到该位置清除杂物能带来的总增益 gain。这样，在所有的杂物格子中找到最大的 gain，加上之前的 ori 即为答案。

统计有哪些荒地恰好被一个杂物挡住的参考代码：

for (________) {
    for (________) {
        if (________) {
            // 这个荒地恰好只有一个杂物邻居，找到它是哪一个
            for (________) {
                 int ni = ________, nj = ________;
                 if (________)
                     cnt[ni][nj]++;  // 位于 ni 行 nj 列的杂物位置“挡住”了一块荒地
            }
        }
    }
}

统计每个荒地清楚后带来的增益，并且求出最大增益的参考代码：

for (________) {
    for (________) {
        if (________) {
            int gain = cnt[i][j];  // 来自周围荒地的增益
            // 再看看它自己变成荒地后，周围有没有别的 '#'，请仿照给出的第一段代码，完成这一部分。

            if (________) gain++;  // 它自己也能开垦
            ________; // 更新最大增益
        }
    }
}
// 最后，需要输出什么作为答案呢？

这样，我们就在 O(nm) 的时间复杂度下完成了这个试题。