Q. [GESP202503 四级] 荒地开垦

Type: RemoteJudge

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小杨有一大片荒地，可以表示为一个 $n$ 行 $m$ 列的网格图。

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

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

第一行包含两个正整数 $n, m$ ，含义如题面所示。

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

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

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

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

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

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

对于全部数据，有 $1\leq n,m\leq 1000$ 。