B4263 [GESP202503 四级] 荒地开垦
题目描述
小杨有一大片荒地，可以表示为一个 n 行 m 列的网格图。
小杨想要开垦这块荒地，但荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。
小杨可以选择至多一个位置，清除该位置的杂物，移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下，最多能够开垦多少块荒地。
输入格式
第一行包含两个正整数 n, m，含义如题面所示。
之后 n 行，每行包含一个长度为 m 且仅包含字符 . 和 # 的字符串。如果为 .，代表该位置为荒地；如果为 #，代表该位置为杂物。
输出格式
输出一个整数，代表在清除至多一个位置的杂物的情况下，最多能够开垦的荒地块数。
输入输出样例 #1
输入 #1
3 5
.....
.#..#
.....
输出 #1
11
说明/提示
样例解释
移除第二行从左数第二块空地的杂物后：
.....
....#
.....
第一行从左数前 4 块荒地，第二行从左数前 3 块荒地，第三行从左数前 4 块荒地，均可开垦，4+3+4=11。
数据范围
对于全部数据，有 1\leq n,m\leq 1000。
蒟蒻的代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
char mp[1005][1005];
bool check(int x, int y){
if (mp[x][y] != '#' && mp[x - 1][y] != '#' && mp[x][y - 1] != '#' && mp[x][y + 1] != '#' && mp[x + 1][y] != '#') return true;
else return false;
}
int check_out(int x, int y){
int sum = 0;
mp[x][y] = '.';
if (check(x - 1, y)) sum ++;
if (check(x, y)) sum ++;
if (check(x, y - 1)) sum ++;
if (check(x, y + 1)) sum ++;
if (check(x + 1, y)) sum ++;
mp[x][y] = '#';
return sum;
}
int main(){
cin >> n >> m;
for (int i = 1;i <= n;++ i)
for (int j = 1;j <= m;++ j)
cin >> mp[i][j];
int maxn = -114514;
for (int i = 1;i <= n;++ i)
for (int j = 1;j <= m;++ j){
if (mp[i][j] == '#' && check_out(i, j) >= maxn)
maxn = check_out(i, j);
}
int res = 0;
for (int i = 1;i <= n;++ i)
for (int j = 1;j <= m;++ j){
if (check(i, j))
res ++;
}
cout << res + maxn << endl;
return 0;
}
dolao们帮我看看拿错了吧，WA 60分,