#1601. GESP四级202503-1荒地开垦

GESP四级202503-1荒地开垦

【问题描述】

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

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

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

【输入描述】

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

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

【输出描述】

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

【样例输入 1】

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

【样例输出 1】

11

样例解释

对于样例 1,

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

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

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

数据范围

对于所有测试点,保证1 <= n,m <= 1000。