#B1344. 荒地开垦 [GESP202503 四级]

荒地开垦 [GESP202503 四级]

【题目描述】

小杨有一大片荒地,可以表示为一个 nn 行 mm 列的网格图。

其中一些格子存在杂物,其余格子为荒地。对于一个不存在杂物的荒地格子,若它在网格内的上下左右相邻格子均不存在杂物,则这块荒地可以被开垦。

小杨至多可以选择一个存在杂物的格子,将其中的杂物清除。清除后,该格子变为荒地。

请你计算,在清除至多一个格子的杂物后,最多能够开垦多少块荒地。


【输入描述】

第一行输入两个整数 n,mn,m,分别表示网格的行数和列数。

接下来 nn 行,每行输入一个长度为 mm 的字符串。字符串仅包含字符 . 和 #:

  • . 表示该位置为荒地;
  • # 表示该位置存在杂物。

保证:

  • 1≤n,m≤10001\le n,m\le 1000。

【输出描述】

输出一个整数,表示在清除至多一个格子的杂物后,最多能够开垦的荒地块数。


【样例 1】

【样例 1 输入】

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

【样例 1 输出】

11

【样例 1 解释】

清除第 22 行从左数第 22 个格子的杂物后,网格变为:

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

此时,第 11 行从左数前 44 个格子、第 22 行从左数前 33 个格子、第 33 行从左数前 44 个格子均可开垦,共有 4+3+4=114+3+4=11 块荒地可以开垦。


【样例 2】

【样例 2 输入】

4 6
..#...
.#..#.
...#..
#.....

【样例 2 输出】

9

【样例 2 解释】

例如,清除第 33 行第 44 列的杂物后,最多有 99 块荒地可以开垦。