题目背景

对应的选择、判断题：试题 - GESP 202503 C++ 四级 - 洛谷有题

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

11

说明/提示

样例解释

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

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

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

数据范围

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

代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, m;
vector<string> g;
vector<vector<int>> cnt;

int calc(int x, int y)
{
    if (g[x][y] != '.') return 0;
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (g[nx][ny] == '#') return 0;
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    g.resize(n);
    cnt.assign(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) cin >> g[i];

    int total = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cnt[i][j] = calc(i, j);
            total += cnt[i][j];
        }
    }

    int ans = total;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (g[i][j] != '#') continue;
            int now = total;
            for (int d = 0; d < 4; d++)
            {
                int nx = i + dx[d], ny = j + dy[d];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (cnt[nx][ny]) now--;
            }
            g[i][j] = '.';
            for (int d = 0; d < 4; d++)
            {
                int nx = i + dx[d], ny = j + dy[d];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                now += calc(nx, ny);
            }
            now += calc(i, j);
            g[i][j] = '#';
            if (now > ans) ans = now;
        }
    }
    cout << ans << endl;
    return 0;
}