202503-荒地开垦(luogu-B4263)

GESP C++四级2025年3月真题。本题主要考查二维数组的应用。解题思路中使用函数封装的思想可以简化思路。整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B4263 [GESP202503 四级] 荒地开垦

题目要求

题目描述

小杨有一大片荒地，可以表示为一个 $n$ 行 $m$ 列的网格图。
小杨想要开垦这块荒地，但荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。
小杨可以选择至多一个位置，清除该位置的杂物，移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下，最多能够开垦多少块荒地。

输入格式

第一行包含两个正整数 $n, m$ ，含义如题面所示。
之后 $n$ 行，每行包含一个长度为 $m$ 且仅包含字符 . 和 # 的字符串。如果为 .，代表该位置为荒地；如果为 #，代表该位置为杂物。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

说明/提示

样例解释

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

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

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

数据范围

对于全部数据，有 $1\leq n,m\leq 1000$ 。

题目分析

本题提供了两种解题思路，分别详细介绍如下：

方法一、原创函数拆分法

这种方法的核心思想是将复杂的判断逻辑拆分成多个独立的函数，使得代码结构清晰，易于理解和维护。

1. 算法核心思想

通过函数封装简化复杂逻辑:

使用check_point函数检查位置是否可开垦
使用check_add_*系列函数检查除某个方向外，周围荒地是否新增可开垦
使用check_*基础函数判断单个方向是否满足开垦条件

遍历策略:

先统计原始可开垦数量
对每个杂物位置模拟清除并计算增益:
- 判断位置自身是否可开垦
- 检查四周荒地是否新增可开垦
记录最大增益并与原始数量相加

相比方法二更注重代码可读性和模块化。

2. 算法复杂度分析

时间复杂度
- 遍历地图计算原始可开垦数量: $O(n \times m)$
- 对每个杂物位置模拟清除:
  - 检查位置本身和周围四个方向: $O(1)$
  - 总共最多有 $n \times m$ 个杂物位置
- 总体时间复杂度: $O(n \times m)$
空间复杂度
- 存储地图数据: $O(n \times m)$
- 其他变量: $O(1)$
- 总体空间复杂度: $O(n \times m)$

方法二：洛谷题解方向数组法

这种方法使用方向数组来简化代码，通过多次遍历优化计算过程，代码更加简洁高效。

1. 算法核心思想

使用方向数组简化四个方向的遍历:

定义行方向数组 di[] 和列方向数组 dj[]
通过循环遍历四个方向，避免重复代码

三次遍历策略:

第一次遍历:
- 计算原始可开垦数量
- 记录每个位置周围杂物数量
第二次遍历:
- 找出只受一个杂物影响的荒地
- 统计每个杂物对周围荒地的影响
第三次遍历:
- 计算清除每个杂物的总收益
- 更新最大增益

2. 算法复杂度分析

时间复杂度
- 三次遍历地图: $O(3 \times n \times m)$
- 每个位置检查四个方向: $O(4)$
- 总体时间复杂度: $O(n \times m)$
空间复杂度
- 存储地图数据: $O(n \times m)$
- 存储杂物计数: $O(n \times m)$
- 存储增益计数: $O(n \times m)$
- 总体空间复杂度: $O(n \times m)$

示例代码

方法一、原创函数拆分法

#include <iostream>

// 存储输入的地图数据
std::string str_ary[1005];

// 检查当前位置左边是否满足开垦条件
// x,y 为当前位置坐标，n,m为地图大小
bool check_left(int x, int y, int n, int m) {
    if (y == 0) {  // 如果在最左边，满足条件
        return true;
    }
    if (str_ary[x][y - 1] == '.') {  // 如果左边是荒地，满足条件
        return true;
    }
    return false;
}

// 检查当前位置右边是否满足开垦条件
bool check_right(int x, int y, int n, int m) {
    if (y == m - 1) {  // 如果在最右边，满足条件
        return true;
    }
    if (str_ary[x][y + 1] == '.') {  // 如果右边是荒地，满足条件
        return true;
    }
    return false;
}

// 检查当前位置上方是否满足开垦条件
bool check_up(int x, int y, int n, int m) {
    if (x == 0) {  // 如果在最上边，满足条件
        return true;
    }
    if (str_ary[x - 1][y] == '.') {  // 如果上方是荒地，满足条件
        return true;
    }
    return false;
}

// 检查当前位置下方是否满足开垦条件
bool check_down(int x, int y, int n, int m) {
    if (x == n - 1) {  // 如果在最下边，满足条件
        return true;
    }
    if (str_ary[x + 1][y] == '.') {  // 如果下方是荒地，满足条件
        return true;
    }
    return false;
}

// 检查当前位置四周是否都满足开垦条件
bool check_point(int x, int y, int n, int m) {
    if (check_left(x, y, n, m) && check_right(x, y, n, m) && check_up(x, y, n, m) && check_down(x, y, n, m)) {
        return true;
    }
    return false;
}

// 检查当前位置除了下方外是否都满足开垦条件
bool check_add_down(int x, int y, int n, int m) {
    if (str_ary[x][y] == '.' && check_left(x, y, n, m) && check_right(x, y, n, m) && check_up(x, y, n, m)) {
        return true;
    }
    return false;
}

// 检查当前位置除了上方外是否都满足开垦条件
bool check_add_up(int x, int y, int n, int m) {
    if (str_ary[x][y] == '.' && check_left(x, y, n, m) && check_right(x, y, n, m) && check_down(x, y, n, m)) {
        return true;
    }
    return false;
}

// 检查当前位置除了右方外是否都满足开垦条件
bool check_add_right(int x, int y, int n, int m) {
    if (str_ary[x][y] == '.' && check_left(x, y, n, m) && check_up(x, y, n, m) && check_down(x, y, n, m)) {
        return true;
    }
    return false;
}

// 检查当前位置除了左方外是否都满足开垦条件
bool check_add_left(int x, int y, int n, int m) {
    if (str_ary[x][y] == '.' && check_right(x, y, n, m) && check_up(x, y, n, m) && check_down(x, y, n, m)) {
        return true;
    }
    return false;
}

int main() {
    int n, m;
    std::cin >> n >> m;  // 输入地图大小
    // 输入地图数据
    for (int i = 0; i < n; i++) {
        std::cin >> str_ary[i];
    }
    int original_count = 0;  // 不清除杂物时可开垦的数量
    int add_count = 0;      // 清除一个杂物后额外增加的可开垦数量
    // 遍历地图的每个位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int temp_count = 0;  // 临时计数器
            if (str_ary[i][j] == '.') {  // 如果当前位置是荒地
                if (check_point(i, j, n, m)) {  // 检查是否可以开垦
                    original_count++;
                }
            } else {  // 如果当前位置是杂物
                // 检查清除当前杂物后，该位置是否可以开垦
                if (check_point(i, j, n, m)) {
                    temp_count++;
                }
                // 检查清除当前杂物后，周围的荒地是否可以开垦
                if (i != 0) {  // 检查上方
                    if (check_add_down(i - 1, j, n, m)) {
                        temp_count++;
                    }
                }
                if (i != n - 1) {  // 检查下方
                    if (check_add_up(i + 1, j, n, m)) {
                        temp_count++;
                    }
                }
                if (j != 0) {  // 检查左方
                    if (check_add_right(i, j - 1, n, m)) {
                        temp_count++;
                    }
                }
                if (j != m - 1) {  // 检查右方
                    if (check_add_left(i, j + 1, n, m)) {
                        temp_count++;
                    }
                }
            }
            // 更新清除杂物后能增加的最大开垦数量
            add_count = std::max(add_count, temp_count);
        }
    } 
    // 输出总的可开垦数量
    std::cout << original_count + add_count;
    return 0;
}

方法二：洛谷题解方向数组法(完整版)

#include <iostream>

// 存储地图数据的字符串数组
std::string str_ary[1005];
// 方向数组,用于遍历上下左右四个方向
const int di[4] = {-1, 1, 0, 0};  // 行方向偏移
const int dj[4] = {0, 0, -1, 1};  // 列方向偏移
// 记录每个位置周围杂物的数量
int bad_count_ary[1005][1005];
// 记录每个杂物位置可以增加的开垦数量
int cnt[1005][1005];

// 检查位置是否越界或为荒地
bool check(int x, int y, int n, int m) {
    if (x < 0 || x >= n || y < 0 || y >= m || str_ary[x][y] == '.') {
        return true;
    }
    return false;
}

// 检查一个位置四周的杂物情况
bool check_point(int x, int y, int n, int m, int& bad_count) {
    for (int i = 0; i < 4; i++) {
        int nx = x + di[i];
        int ny = y + dj[i];
        if (!check(nx, ny, n, m)) {  // 如果周围有杂物
            bad_count++;
        }
    }
    return bad_count > 0 ? false : true;  // 有杂物返回false，无杂物返回true
}

int main() {
    int n, m;
    std::cin >> n >> m;  // 输入地图大小
    // 输入地图数据
    for (int i = 0; i < n; i++) {
        std::cin >> str_ary[i];
    }
    
    int original_count = 0;  // 记录不清除杂物时可开垦的数量
    // 第一次遍历：计算原始可开垦数量和记录每个位置周围的杂物数
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int temp_count = 0;
            int bad_count = 0;
            if (str_ary[i][j] == '.' && check_point(i, j, n, m, bad_count)) {
                original_count++;  // 如果是可开垦的荒地，计数加1
            }
            bad_count_ary[i][j] = bad_count;  // 记录周围杂物数
        }
    }
    
    // 第二次遍历：统计每个杂物位置对周围荒地的影响
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果是只受一个杂物影响的荒地
            if (str_ary[i][j] == '.' && bad_count_ary[i][j] == 1) {
                // 找到影响它的那个杂物，并增加该杂物的计数
                for (int k = 0; k < 4; k++) {
                    int nx = i + di[k];
                    int ny = j + dj[k];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                        str_ary[nx][ny] == '#')
                        cnt[nx][ny]++;  // 该杂物位置的增益计数加1
                }
            }
        }
    }
    
    int best = 0;  // 记录清除一个杂物后最大的增益
    // 第三次遍历：计算清除每个杂物位置能获得的最大增益
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (str_ary[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 &&
                        str_ary[ni][nj] == '#')
                        bad++;  // 统计周围杂物数
                }
                if (bad == 0) {
                    gain++;    // 它自己也能开垦
                }
                best = std::max(best, gain);  // 更新最大增益
            }
        }
    }
    
    // 输出最终结果：原始可开垦数量 + 清除一个杂物后的最大增益
    std::cout << original_count + best;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号

最后更新于 2025年9月15日

202412-字符排序(luogu-B4069)202503-二阶矩阵(luogu-B4264)