#B1344. 荒地开垦 [GESP202503 四级]
荒地开垦 [GESP202503 四级]
【题目描述】
小杨有一大片荒地,可以表示为一个 行 列的网格图。
其中一些格子存在杂物,其余格子为荒地。对于一个不存在杂物的荒地格子,若它在网格内的上下左右相邻格子均不存在杂物,则这块荒地可以被开垦。
小杨至多可以选择一个存在杂物的格子,将其中的杂物清除。清除后,该格子变为荒地。
请你计算,在清除至多一个格子的杂物后,最多能够开垦多少块荒地。
【输入描述】
第一行输入两个整数 ,分别表示网格的行数和列数。
接下来 行,每行输入一个长度为 的字符串。字符串仅包含字符 . 和 #:
.表示该位置为荒地;#表示该位置存在杂物。
保证:
- 。
【输出描述】
输出一个整数,表示在清除至多一个格子的杂物后,最多能够开垦的荒地块数。
【样例 1】
【样例 1 输入】
3 5
.....
.#..#
.....
【样例 1 输出】
11
【样例 1 解释】
清除第 行从左数第 个格子的杂物后,网格变为:
.....
....#
.....
此时,第 行从左数前 个格子、第 行从左数前 个格子、第 行从左数前 个格子均可开垦,共有 块荒地可以开垦。
【样例 2】
【样例 2 输入】
4 6
..#...
.#..#.
...#..
#.....
【样例 2 输出】
9
【样例 2 解释】
例如,清除第 行第 列的杂物后,最多有 块荒地可以开垦。