4676: 【GESP2503四级】荒地开垦

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

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

输入

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

输出

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

样例输入 复制 

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

样例输出 复制 

11

提示

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
char mat[N][N];
int a[N][N];
const int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int main() {
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    assert(1 <= n && n <= 1000);
    assert(1 <= m && m <= 1000);
    for (int i = 1; i <= n; i ++)
        scanf("%s", mat[i] + 1);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            int num = 0, p = -1;
            for (int k = 0; k < 4; k ++)
                if (mat[i + d[k][0]][j + d[k][1]] == '#')
                    num ++, p = k;
            if (mat[i][j] == '.' && num == 1)
                a[i + d[p][0]][j + d[p][1]] ++;
            else if (mat[i][j] == '.' && num == 0)
                ans ++;
            else if (mat[i][j] == '#' && num == 0)
                a[i][j] ++;
        }
    int mx = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= m; j ++)
            mx = max(mx, a[i][j]);
    cout << ans + mx << endl;
    return 0;
}

来源/分类

提交提交记录统计露一手!