当前位置：首页 > news >正文

B4263 [GESP202503 四级] 荒地开垦题解

news 2025/8/11 13:19:41

题目传送门：B4263 [GESP202503 四级] 荒地开垦

题目描述

小杨有一大片荒地，可以表示为一个 n 行 m 列的网格图。

小杨想要开垦这块荒地，但荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。

小杨可以选择至多一个位置，清除该位置的杂物，移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下，最多能够开垦多少块荒地。

输入格式

第一行包含两个正整数 n,m，含义如题面所示。

之后 n 行，每行包含一个长度为 m 且仅包含字符 . 和 # 的字符串。如果为 .，代表该位置为荒地；如果为 #，代表该位置为杂物。

输出格式

输出一个整数，代表在清除至多一个位置的杂物的情况下，最多能够开垦的荒地块数。

输入输出样例

输入 #1复制

3 5
.....
.#..#
.....

输出 #1复制

说明/提示

样例解释

移除第二行从左数第二块空地的杂物后：

.....
....#
.....

第一行从左数前 4 块荒地，第二行从左数前 3 块荒地，第三行从左数前 4 块荒地，均可开垦，4+3+4=11。

数据范围

对于全部数据，有 1≤n,m≤1000。

以下是题解：

题目分析

‌问题理解‌：我们需要在n×m的网格中找到移除一个杂物后能开垦的最大荒地数量。开垦条件是该荒地及其上下左右四个相邻格子都没有杂物。
‌关键观察‌：
- 初始状态下，一个荒地可开垦当且仅当它和四个相邻格子都是荒地
- 移除一个杂物可能影响：
  - 该位置本身可能成为新的可开垦荒地
  - 周围4个荒地可能从不可开垦变为可开垦
‌优化思路‌：
- 预处理每个荒地周围的杂物数量
- 记录初始可开垦荒地总数
- 对每个杂物，计算移除它能带来的净增益

算法设计

‌预处理阶段‌：
- 遍历网格，统计每个荒地周围的杂物数量
- 计算初始可开垦荒地数量（周围杂物数为0的荒地）
‌杂物处理阶段‌：
- 对每个杂物位置：
  - 计算移除后能新增的可开垦荒地数
  - 计算移除后可能失去的原可开垦荒地数
  - 计算净增益并更新最大值
‌时间复杂度‌：O(nm)，适用于1000×1000的网格

C++代码实现

#include <iostream>
#include <vector>
using namespace std;const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;vector<string> grid(n);for (int i = 0; i < n; ++i) {cin >> grid[i];}vector<vector<int>> cnt(n, vector<int>(m, 0));int total = 0;// 预处理每个荒地周围的杂物数量for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == '#') continue;int c = 0;for (int k = 0; k < 4; ++k) {int ni = i + dx[k], nj = j + dy[k];if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '#') {c++;}}cnt[i][j] = c;if (c == 0) total++;}}int max_farm = total;// 检查每个杂物位置for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] != '#') continue;int potential = 0;vector<pair<int, int>> affected;// 检查移除该杂物后能新增多少可开垦荒地for (int k = 0; k < 4; ++k) {int ni = i + dx[k], nj = j + dy[k];if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '.') {if (cnt[ni][nj] == 1) {potential++;}affected.emplace_back(ni, nj);}}// 检查当前位置本身是否能成为可开垦荒地bool self_farmable = true;for (int k = 0; k < 4; ++k) {int ni = i + dx[k], nj = j + dy[k];if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '#') {self_farmable = false;break;}}if (self_farmable) potential++;// 检查移除该杂物后会影响多少原有可开垦荒地int lost = 0;for (auto [x, y] : affected) {if (cnt[x][y] == 0) lost++;}max_farm = max(max_farm, total + potential - lost);}}cout << max_farm << endl;return 0;
}

代码特点：