可清除至多一个杂物,求最多能开垦多少块荒地(该格及其四邻都无杂物)。
荒地是 n 行 m 列的网格,. 表示荒地、# 表示杂物。
一块无杂物的荒地可以开垦,当且仅当其上下左右四个方向相邻的格子均不存在杂物。
小杨可以选择至多一个位置清除杂物,清除后该位置变为荒地。求最多能开垦多少块荒地。
# 后,只有它自己以及它上下左右 4 个邻居的开垦状态可能变化。所以我们只需对这 5 个格子重新判断,不用把整个网格重算一遍。四邻判定局部影响范围预处理 - 增量计算网格
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 n 行含 . 和 # 的字符串 |
| 输出 | 清除至多一个杂物后,最多能开垦的块数 |
| 数据范围 | 1 ≤ n, m ≤ 1000 |
| 开垦条件 | 该格为 .,且四邻(上下左右)都无杂物 |
| 清除限制 | 至多一个(也可以不清除) |
. 检查四邻# 后谁会变?只有它自己和四个邻居——因为其他格子的邻域没有变化..... .#..# .....
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
受影响的 5 格:(2,2) 自己 + (1,2)、(2,1)、(2,3)、(3,2)
这 5 格原先都不能开垦
清除后 (2,2) 变成荒地,这 5 格的四邻都不再含杂物
于是 5 格全部变得可以开垦 → 增量 +5
6 + 5 = 11
受影响的格:(2,5) 自己 + (1,5)、(2,4)、(3,5)(右侧越界)
这 4 格原先都不能开垦,清除后全部可以 → 增量 +4
6 + 4 = 10
清除 (2,2) 得 11 块;清除 (2,5) 得 10 块
不清除任何杂物得 6 块
三者取最大
✅ 输出 11
(2,4) 虽然是 .,但它的邻居 (2,5) 是杂物,所以不能开垦;同理 (1,5)、(3,5) 也因 (2,5) 而不能开垦。光看出网格是 . 是不够的,必须逐格检查四邻。这是本题的算法核心,务必理解。
取决于"它自己是否是杂物"和"四邻是否有杂物"
也就是只与它自己和上下左右 4 格有关
影响范围 = 自己 + 上下左右
设清除位置为 p
只有"其开垦状态的计算涉及 p"的格子才可能变化
满足条件的格子 = p 自己 + p 的上下左右 4 邻
共 5 格(边界处更少)
受影响的格子最多 5 个
对每个杂物位置 p:临时清除它
只重新判断这 5 格的开垦状态
增量 = (新可开垦数)−(原本可开垦数)
取所有 p 的最大增量,再与 baseline 取最大
总体 O(nm × 5),非常快
这比"每次重算整个网格"快了 n×m 倍
预处理 baseline,对每个杂物只重算 5 格
枚举杂物位置,每次都把整个网格的开垦数重算一遍
| 方案 | 运算量(1000×1000) | 是否可行 |
|---|---|---|
| 局部增量 | 约 5 × 10⁶ | ✅ 可行 |
| 全图重算 | 约 10¹² | ❌ 超时 |
第一行输入 n 和 m,随后 n 行由 . 和 # 组成的网格。程序会尝试清除每个杂物。
点按钮开始 →
#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);② 清除后忘记还原,导致后续枚举基于错误的网格;③ 忽略". 不代表一定能开垦"——必须检查四邻,本题最容易数错的就是这一点。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 5 | 11 | 题面样例 |
1 1 | 1 | 单格荒地,无邻居 |
1 1 | 1 | 单格是杂物,清除后变成可开垦 |
1 3 | 3 | 清除中间杂物后三格全部可开垦 |
2 2 | 4 | 本身全部可开垦,不需要清除 |
. 都当成可开垦:必须检查它的四邻是否都是 .,本题最容易数错的就是这一步。需要存整个字符网格,10⁶ 字节。
✅ 约 500 万次判断,瞬间完成。如果对每个杂物都重算全图,会变成 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};
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 局部影响范围 | 状态只依赖有限邻域 | 扫雷、生命游戏、网格增量更新 |
| 预处理 + 增量 | 先算基准值,再算增量 | 所有"修改一次求最优"的题目 |
| 边界四邻 | 越界就跳过 | 所有网格题目的必备写法 |