GESP 题解库 / 4 级题解 / [GESP202503 四级] 荒地开垦 · 第 10 / 25 题
GESP202503 四级 · B4263 · 简单

荒地开垦

可清除至多一个杂物,求最多能开垦多少块荒地(该格及其四邻都无杂物)。

📊
n, m ≤ 1000
网格规模
🔢
int
数值类型
⚡
O(n × m)
时间复杂度
🎯
局部重算
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

荒地是 n 行 m 列的网格,. 表示荒地、# 表示杂物。

一块无杂物的荒地可以开垦,当且仅当其上下左右四个方向相邻的格子均不存在杂物。

小杨可以选择至多一个位置清除杂物,清除后该位置变为荒地。求最多能开垦多少块荒地。

💡
人话翻译:先数一遍现在能开垦多少块。然后考虑"挖掉哪个杂物最划算"——挖掉一个 # 后,只有它自己以及它上下左右 4 个邻居的开垦状态可能变化。所以我们只需对这 5 个格子重新判断,不用把整个网格重算一遍。

🔍 关键词提取

四邻判定局部影响范围预处理 - 增量计算网格

已知条件

项目说明
输入第一行 n、m;随后 n 行含 . 和 # 的字符串
输出清除至多一个杂物后,最多能开垦的块数
数据范围1 ≤ n, m ≤ 1000
开垦条件该格为 .,且四邻(上下左右)都无杂物
清除限制至多一个(也可以不清除)

需要解决的问题

02
思维导图
整理解题思路的全貌
🌱 预处理 + 只重算 5 格
📥 读入
n、m ≤ 1000
字符矩阵
10⁶ 个格子
用 char 数组存
🔢 预处理
定义 ok(i,j):该格可开垦
遍历全图求 baseline
O(nm)
同时把结果存进 bool 数组
🔄 枚举清除点
对每个 # 位置 p
临时把 p 变成 .
只重算 p 和它的 4 邻
增量 = 新可开垦 − 原有的
📤 取最优
ans = max(baseline, baseline + 各增量)
注意也允许不清除
复杂度 O(nm)
不要每题重算全图
03
样例手算推导
样例 3×5 网格的增量分析

🧮 样例:答案 11

.....
.#..#
.....
1
第 1 步:数清哪些格不能开垦

15 格中有 2 个杂物((2,2)、(2,5)),剩 13 个荒地候选

逐个检查四邻后,不能开垦的有 7 格:

(1,2)、(1,5)、(2,1)、(2,3)、(2,4)、(3,2)、(3,5)

其中 (1,2)、(2,1)、(2,3)、(3,2) 是被 (2,2) 挡住的

(1,5)、(2,4)、(3,5) 是被 (2,5) 挡住的

baseline = 13 − 7 = 6

2
第 2 步:试清除 (2,2)

受影响的 5 格:(2,2) 自己 + (1,2)、(2,1)、(2,3)、(3,2)

这 5 格原先都不能开垦

清除后 (2,2) 变成荒地,这 5 格的四邻都不再含杂物

于是 5 格全部变得可以开垦 → 增量 +5

6 + 5 = 11

3
第 3 步:试清除 (2,5)

受影响的格:(2,5) 自己 + (1,5)、(2,4)、(3,5)(右侧越界)

这 4 格原先都不能开垦,清除后全部可以 → 增量 +4

6 + 4 = 10

4
第 4 步:取最大值

清除 (2,2) 得 11 块;清除 (2,5) 得 10 块

不清除任何杂物得 6 块

三者取最大

✅ 输出 11

🔑
这题最容易错的地方不是算法,而是"数错 baseline"。本样例中最容易被漏掉的是:(2,4) 虽然是 .,但它的邻居 (2,5) 是杂物,所以不能开垦;同理 (1,5)、(3,5) 也因 (2,5) 而不能开垦。光看出网格是 . 是不够的,必须逐格检查四邻。

🧮 增量算法的核心:为什么只需重算 5 格

这是本题的算法核心,务必理解。

1
一个格子的开垦状态取决于什么?

取决于"它自己是否是杂物"和"四邻是否有杂物"

也就是只与它自己和上下左右 4 格有关

影响范围 = 自己 + 上下左右

2
清除一个杂物会影响哪些格子?

设清除位置为 p

只有"其开垦状态的计算涉及 p"的格子才可能变化

满足条件的格子 = p 自己 + p 的上下左右 4 邻

共 5 格(边界处更少)

受影响的格子最多 5 个

3
所以算法是

对每个杂物位置 p:临时清除它

只重新判断这 5 格的开垦状态

增量 = (新可开垦数)−(原本可开垦数)

取所有 p 的最大增量,再与 baseline 取最大

总体 O(nm × 5),非常快

这比"每次重算整个网格"快了 n×m 倍

04
解法对比
局部增量 vs 每次重算全图

⚔️ 解法对比

🟢 局部增量(推荐) 推荐

预处理 baseline,对每个杂物只重算 5 格

  • 时间 O(n × m)
  • 10⁶ 格 → 约 5 × 10⁶ 次
  • 关键在于"影响范围只有 5 格"
  • 代码稍长但可行
💡
核心洞察:"一个格子的开垦状态只依赖它自己和四邻",所以清除一个杂物只会改变 5 个格子的状态。这是把 O(nm × nm) 降到 O(nm) 的关键。

🟠 对每个杂物重算全图

枚举杂物位置,每次都把整个网格的开垦数重算一遍

  • 时间 O(n²m²)
  • n = m = 1000 时约 10¹² 次
  • 必然超时
  • 思路简单但不可行
⚠️
注意:如果 n、m 很小(比如 ≤ 10),这种暴力写法完全没问题;但本题 n、m ≤ 1000,必须利用"影响范围有限"这一性质。

📈 性能对比

方案运算量(1000×1000)是否可行
局部增量约 5 × 10⁶✅ 可行
全图重算约 10¹²❌ 超时
05
算法流程图
预处理 baseline → 枚举杂物 → 局部重算
开始读入 n、m 和字符网格遍历全图,计算每格是否可开垦,得到 baseline枚举每个杂物位置 p临时把 p 改为荒地,重算 p 及其四邻这 5 格的开垦状态增量能得到更大的总数吗?是 ✓更新答案否 ✗保留原答案把 p 恢复为杂物输出 max(baseline, 各尝试的最大值)结束还有杂物 → 继续尝试清除
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌱 荒地开垦最大化器

第一行输入 n 和 m,随后 n 行由 . 和 # 组成的网格。程序会尝试清除每个杂物。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
char g[1005][1005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = { 0, 0,-1, 1};

// 判断 (i, j) 是否可以开垦
bool canTill(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m) return false;
    if (g[i][j] != '.') return false;
    for (int d = 0; d < 4; d++) {
        int ni = i + dx[d], nj = j + dy[d];
        if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
        if (g[ni][nj] != '.') return false;   // 邻居有杂物
    }
    return true;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", g[i]);

    // 1) 预处理:不清除任何杂物时的可开垦数
    int base = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (canTill(i, j)) base++;

    int ans = base;      // 允许"不清除"

    // 2) 枚举清除每个杂物,只重算它自己和四邻
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] != '#') continue;

            // 记录受影响的 5 格原本的可开垦情况
            int oldCnt = 0, newCnt = 0;
            int pi[5], pj[5], cnt = 0;
            pi[cnt] = i; pj[cnt] = j; cnt++;
            for (int d = 0; d < 4; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
                pi[cnt] = ni; pj[cnt] = nj; cnt++;
            }
            for (int k = 0; k < cnt; k++) if (canTill(pi[k], pj[k])) oldCnt++;

            // 清除杂物后重新计算这 5 格
            g[i][j] = '.';
            for (int k = 0; k < cnt; k++) if (canTill(pi[k], pj[k])) newCnt++;
            g[i][j] = '#';                       // 还原

            if (base - oldCnt + newCnt > ans) ans = base - oldCnt + newCnt;
        }
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么用 base − oldCnt + newCnt?因为这 5 格里原本可能已经有一些是可开垦的,直接写 base + (newCnt − oldCnt) 更清楚。关键是要先统计"原本可开垦数",再统计"清除后可开垦数",两者之差才是净增量。

📖 关键几行怎么看

代码作用为什么这样写
canTill(i, j)判断单格可开垦把判定封装成函数,便于反复调用
int ans = base;允许不清除题目说"至多一个",所以不清除也是合法选择
pi[cnt] = i; pj[cnt] = j; cnt++;收集受影响格把 p 自己和四邻共 5 格(可能更少)存起来
g[i][j] = '#';还原尝试完必须恢复,否则影响后续枚举
⚠️
三个坑:① 忘记"允许不清除"(ans 应初始化为 base);② 清除后忘记还原,导致后续枚举基于错误的网格;③ 忽略". 不代表一定能开垦"——必须检查四邻,本题最容易数错的就是这一点。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 5
..... / .#..# / .....
11题面样例
1 1
.
1单格荒地,无邻居
1 1
#
1单格是杂物,清除后变成可开垦
1 3
.#.
3清除中间杂物后三格全部可开垦
2 2
.. / ..
4本身全部可开垦,不需要清除
✅
自查清单:① 单格判定检查四邻了吗?② ans 初始化为 baseline 了吗?③ 只重算了受影响的 5 格吗?

🚨 易错点清单

⚠️
把 . 都当成可开垦:必须检查它的四邻是否都是 .,本题最容易数错的就是这一步。
⚠️
忘记"可以不清除":如果所有清除尝试都让结果变差,应输出 baseline(题目说"至多一个")。
⚠️
对每个杂物重算全图:n, m ≤ 1000 时会超时,必须利用"影响范围只有 5 格"。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × m)
空间复杂度
O(n × m)
n, m 最大
1000
最坏运算
约 5 × 10⁶

时间怎么算的?

空间都用在哪?

需要存整个字符网格,10⁶ 字节。

✅ 约 500 万次判断,瞬间完成。如果对每个杂物都重算全图,会变成 10¹² 次,必然超时。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 网格题的"影响范围"思维
// 问:修改一个格子的值,会影响周围多少个格子的状态?
// 答:取决于"状态的依赖范围"
//   本题:状态依赖"自己 + 四邻" -> 影响范围 = 自己 + 四邻 = 5 格
//   若是"自己 + 8 邻" -> 影响范围 = 9 格

// 通用模板:增量计算
int base = computeAll();
int ans = base;
for (每个可修改位置 p) {
    applyChange(p);
    int delta = recomputeLocally(p);   // 只重算受影响的范围
    ans = max(ans, base + delta);
    revertChange(p);
}

// 4 邻与 8 邻方向数组
int dx4[4] = {-1, 1, 0, 0},  dy4[4] = { 0, 0,-1, 1};
int dx8[8] = {-1,-1,-1,0,0,1,1,1}, dy8[8] = {-1,0,1,-1,1,-1,0,1};

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
局部影响范围状态只依赖有限邻域扫雷、生命游戏、网格增量更新
预处理 + 增量先算基准值,再算增量所有"修改一次求最优"的题目
边界四邻越界就跳过所有网格题目的必备写法
🌟
思考题:如果题目改成可以清除两个杂物,还能用"只重算 5 格"的技巧吗?(提示:会变复杂得多——两个杂物若相邻,影响范围会重叠;一种可行思路是枚举所有相邻的杂物对,对每对考虑"重叠部分只算一次",但更常见的是用"每个位置单独的最优增量 + 组合修正"来处理,难度会明显上升。)