Problem O: 【GESP4】荒地开垦
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:23
Solved:7
Description
小杨有一大片荒地,可以表为一个n行m 列的网格图。
小杨想要开垦这块荒地,但荒地中有一些位置存在杂物,对于一块不存在杂物的荒地,该荒地可以开垦当且仅当其上下左右四个方向相邻的网格均不存在杂物。
小杨可以选择至多一个位置,清除该位置的杂物,移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下,最多能够开垦多少块荒地。
Input
第一行包含两个正整数 ,含义如题所示。
之后 ,每行包含一个长度为m 且仅包含字符 . 和 # 的字符串。如果为 . ,代表该位置为荒地,如果为 # ,代表该位置为杂物。
Output
输出一个整数,代表在清除至多一个位置的杂物的情况下,最多能够开垦的荒地块数。
Sample Input Copy
3 5
. . . . .
.#. .#
. . . . .
Sample Output Copy
11
HINT
样例解释:
移除第从左数第块空地的杂物后:
. . . . .
. . . .#
. . . . .
第一行从左数前 4 块荒地,第二行从左数前 3 块荒地,第三行从左数前 4 块荒地,均可开垦,总计有 4+3+4=11 。
对于全部数据,保证有 1=< n,m =<1000。