简答题
偏难
#20510
荒地开垦 时间限制: 1.0 s 内存限制 :512.0 MB 题面描述 小杨有—大片荒地,可以表⽰为—个n行m列的网格图。 小杨想要开垦这块荒地,但荒地中—些…
荒地开垦
时间限制: 1.0 s
内存限制 :512.0 MB
题面描述
小杨有—大片荒地,可以表⽰为—个n行m列的网格图。
小杨想要开垦这块荒地,但荒地中—些位置存在杂物,对于—块不存在杂物的荒地,该荒地可以开垦当且仅当其 上、下、左、右四个方向相邻的格子均不存在杂物。
小杨可以选择至多—个位置,清除该位置的杂物,移除杂物后该位置变为荒地。小杨想知道在清除至多—个位置的 杂物的情况下,最多能够开垦多少块荒地。
输入格式
第—行包含两个正整数 n , m ,含义如题面所⽰。
之后 n 行,每行包含—个长度为 m 且仅包含字符 . 和 # 的字符串。如果为 . ,代表该位置为荒地;如果为# ,代表该位置为杂物。
输出格式
输出—个整数,代表在清除至多—个位置的杂物的情况下,最多能够开垦的荒地块数。
输入样例
输出样例
样例解释
移除第二行从左数第二块空地的杂物后:
第—行从左数前 4 块荒地,第二行从左数前 3 块荒地,第三行从左数前 4 块荒地,均可开垦, 4 + 3 + 4 = 11。
数据范围
对于全部数据,保证有 1 ≤ n, m ≤ 1000 。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre><p><br/></p>
解析
遍历全图,先找到所有不需要移除杂物即可开垦的荒地数量,另外构建数组a表示移除该点的杂物可 以激活的荒地数量,最后找到a数组中的最大值,就是我们要移除杂物的位置,把最大值更新到答案中就是我们要 的最终答案。