简答题 偏难
#20510

荒地开垦 时间限制: 1.0 s 内存限制 :512.0 MB 题面描述 小杨有—大片荒地,可以表⽰为—个n行m列的网格图。 小杨想要开垦这块荒地,但荒地中—些…

荒地开垦

时间限制: 1.0 s

内存限制 :512.0 MB

题面描述

小杨有—大片荒地,可以表⽰为—个n行m列的网格图。

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

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

输入格式

第—行包含两个正整数  n ,  m ,含义如题面所⽰。

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

输出格式

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

输入样例

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

输出样例

11

样例解释

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

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

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

数据范围

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

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; 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", &amp;n, &amp;m); assert(1 &lt;= n &amp;&amp; n &lt;= 1000); assert(1 &lt;= m &amp;&amp; m &lt;= 1000); for (int i = 1; i &lt;= n; i ++) scanf("%s", mat[i] + 1); for (int i = 1; i &lt;= n; i ++) for (int j = 1; j &lt;= m; j ++) { int num = 0, p = -1; for (int k = 0; k &lt; 4; k ++) if (mat[i + d[k][0]][j + d[k][1]] == '#') num ++, p = k; if (mat[i][j] == '. ' &amp;&amp; num == 1) a[i + d[p][0]][j + d[p][1]] ++; else if (mat[i][j] == '. ' &amp;&amp; num == 0) ans ++; else if (mat[i][j] == '#' &amp;&amp; num == 0) a[i][j] ++; } int mx = 0; for (int i = 1; i &lt;= n; i ++) for (int j = 0; j &lt;= m; j ++) mx = max(mx, a[i][j]); cout &lt;&lt; ans + mx &lt;&lt; endl; return 0; }</pre><p><br/></p>
解析

遍历全图,先找到所有不需要移除杂物即可开垦的荒地数量,另外构建数组a表示移除该点的杂物可 以激活的荒地数量,最后找到a数组中的最大值,就是我们要移除杂物的位置,把最大值更新到答案中就是我们要 的最终答案。