B4263 [GESP202503 四级] 荒地开垦

· · 题解

欢迎报名洛谷网校，期待和大家一起进步！

:::align{center} :::

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

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

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

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

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

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (g[i][j] == '.') {
            int bad = 0; // 周围有多少个杂物
            for (int k = 0; k < 4; k++) {
                int ni = i + di[k], nj = j + dj[k];
                if (ni >= 0 && ni < n && nj >= 0 && nj < m && g[ni][nj] == '#')
                    bad++;
            }
            d[i][j] = bad;
            if (bad == 0) ori++;  // 周围没杂物，能直接开垦
        }
    }
}

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

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

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

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

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (g[i][j] == '.' && d[i][j] == 1) {
            // 这个荒地恰好只有一个杂物邻居，找到它是哪一个
            for (int k = 0; k < 4; k++) {
                 int ni = i + di[k], nj = j + dj[k];
                 if (ni >= 0 && ni < n && nj >= 0 && nj < m && g[ni][nj] == '#')
                     cnt[ni][nj]++;  // 位于 ni 行 nj 列的杂物位置“挡住”了一块荒地
            }
        }
    }
}

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

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (g[i][j] == '#') {
            int gain = cnt[i][j];  // 来自周围荒地的增益
            // 再看看它自己变成荒地后，周围有没有别的 '#' 
            int bad = 0;
            for (int k = 0; k < 4; k++) {
                int ni = i + di[k], nj = j + dj[k];
                if (ni >= 0 && ni < n && nj >= 0 && nj < m && g[ni][nj] == '#')
                        bad++;
            }
            if (bad == 0) gain++;  // 它自己也能开垦
            best = max(best, gain); // 更新最大增益
        }
    }
}

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