荒地开垦 题解

题目分析

我们有一个 $n$ 行 $m$ 列的网格，每个格子要么是荒地（.），要么是杂物（#）。
一块荒地可以被开垦，当且仅当它上下左右四个相邻格子都不是杂物（即网格边界外的位置视为没有杂物）。

小杨可以至多清除一个杂物格子（将其变成荒地），问在此条件下，最多能开垦多少块荒地。

也就是说，我们可以在原始地图上选择一个杂物清除，也可以什么都不做，要使最终满足条件的荒地数量最大化。

解题思路

我们可以把问题拆成两部分：

1. 初始局面：在不清理任何杂物的前提下，直接统计出已经可以开垦的荒地数量，记作 ans。
2. 清除一个杂物的额外收益：枚举每个可能被清除的杂物格子，计算清除它以后，能够新增多少块可开垦的荒地。记某个杂物格子被清除后新增的数量为 a[i][j]，那么最终答案就是 ans + max(a[i][j])（若没有杂物可清除，则最大值取 0，相当于不清除）。

接下来的关键是如何准确计算“清除某个杂物带来的新增可开垦荒地数”。

新增可开垦荒地的来源

当我们清除一个杂物格子 (x, y) 后，影响范围只限于它本身和它上下左右的四个邻居。新增的可开垦荒地只能来自两类：

• 原本受该杂物“阻挡”的荒地：某块荒地原本因为存在该杂物而不满足“周围无杂物”的条件，清除后刚好满足。这要求该荒地原本有且仅有这一个杂物邻居。
• 该杂物自身变成荒地：如果这个杂物格子清除后，它的四个邻居本身没有杂物，那么它自己也会变成一块可开垦的荒地。

一个杂物格子可能同时让多个荒地变得可开垦，因此我们需要对它周围的所有荒地进行检查，累加贡献。

算法说明

我们定义一个二维数组 a[N][N]，初始全 0。a[i][j] 表示如果清除位于 (i, j) 的杂物，能够额外获得的可开垦荒地块数。

遍历网格中的每一个格子 (i, j)，根据它的类型分情况处理。

为了方便处理边界，我们可以在网格周围留出一圈不存在的“虚空”，并且保证它们不是杂物（全局数组默认值为 0，不等于 #）。

情况一：当前格子为荒地（.）

检查其上下左右四个邻居中的杂物数量，记作 num，同时记录第一个杂物邻居的方向（用于定位杂物坐标）。

• 若 num == 0：这块荒地原本就是可开垦的，ans 加 1。
• 若 num == 1：这块荒地当前不可开垦，但如果我们清除那个唯一的杂物邻居，它就变得可开垦了。因此，我们对那个杂物格子的 a 值加 1（表示清除它能多获得这块荒地）。
• 若 num >= 2：即使清除一个杂物，仍有其他杂物邻居，这块荒地永远无法开垦，忽略。

情况二：当前格子为杂物（#）

检查其四个邻居中的杂物数量 num。

• 若 num == 0：说明这个杂物周围没有其他杂物。清除它之后，它自身变成荒地且周围无杂物，因此它自己会变成一块可开垦的荒地。将 a[i][j] 加 1。
• 若 num >= 1：即使清除了这个杂物，它自身变成荒地后周围仍有杂物，自身无法开垦。而周围的荒地是否受益，已经在情况一的“num == 1”逻辑中被统计了，这里不做额外处理。

汇总答案

完成遍历后，a 数组中存储了清除每个杂物格子能带来的额外荒地数量。找出最大值 mx，最终答案即为 ans + mx。

时间复杂度分析

我们只对网格进行了常数次遍历，每个格子只检查了四个方向的邻居。
总时间复杂度为 $O(n \times m)$。
空间上需要存储原始地图和一个同样大小的 a 数组，空间复杂度也为 $O(n \times m)$。
对于 $n, m \leq 1000$ 的数据规模可以轻松通过。

参考代码

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1005;
5char mat[N][N];  // 存储地图
6int a[N][N];     // a[i][j] 表示清除 (i,j) 杂物能额外获得的荒地数
7const int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四个方向
8
9int main() {
10    int n, m, ans = 0;
11    scanf("%d%d", &n, &m);
12
13    // 读入地图，下标从 1 开始，四周默认为 '\0'，不是 '#'
14    for (int i = 1; i <= n; i++)
15        scanf("%s", mat[i] + 1);
16
17    for (int i = 1; i <= n; i++) {
18        for (int j = 1; j <= m; j++) {
19            int num = 0, p = -1; // num：周围杂物数，p：第一个杂物方向
20            for (int k = 0; k < 4; k++) {
21                if (mat[i + d[k][0]][j + d[k][1]] == '#') {
22                    num++;
23                    p = k;        // 记录最后一个杂物方向，不影响功能
24                }
25            }
26            if (mat[i][j] == '.') {
27                if (num == 0) {
28                    ans++;        // 原本就可开垦
29                } else if (num == 1) {
30                    // 清除唯一的杂物邻居即可让该荒地可开垦
31                    a[i + d[p][0]][j + d[p][1]]++;
32                }
33            } else { // mat[i][j] == '#'
34                if (num == 0) {
35                    // 清除后自身变成可开垦荒地
36                    a[i][j]++;
37                }
38            }
39        }
40    }
41
42    int mx = 0;
43    for (int i = 1; i <= n; i++)
44        for (int j = 1; j <= m; j++)
45            mx = max(mx, a[i][j]);
46
47    cout << ans + mx << endl;
48    return 0;
49}

代码解释

• mat 数组下标从 1 开始存储地图，这样四周会自然留出一圈 0（即 '\0'），判断是否为杂物时不会误判。
• d 数组定义了向上下左右四个方向移动的坐标偏移量。
• 第一重循环枚举每个格子，统计其周围四个方向的杂物数量 num，并用 p 记录其中一个杂物所在的方向（在 num == 1 时用于定位障碍物）。
• 若当前为荒地且周围无杂物，直接计入答案；若恰好有一个杂物，说明该杂物是目前唯一的“阻碍”，清除后这块荒地立刻可开垦，因此在 a 中给对应杂物位置加 1。
• 若当前为杂物且周围无杂物，清除它后自己就会变成一块合法荒地，给 a[i][j] 加 1。
• 最后遍历 a 数组取最大值，与 ans 相加输出即可。

这种做法的核心在于：将“清除杂物”这一操作的影响局部化，通过一次扫描完成所有贡献的累加，避免了对每个杂物进行模拟的高昂代价。