A4902. [GESP202503 四级] 荒地开垦
编程题
普及-
知识点
题目描述
小杨有一大片荒地,可以表示为一个 $n$ 行 $m$ 列的网格图｡
小杨想要开垦这块荒地,但荒地中一些位置存在杂物,对于一块不存在杂物的荒地,该荒地可以开垦当且仅当其上 下左右四个方向相邻的格子均不存在杂物｡
小杨可以选择至多一个位置,清除该位置的杂物,移除杂物后该位置变为荒地｡小杨想知道在清除至多一个位置的 杂物的情况下,最多能够开垦多少块荒地｡
小杨想要开垦这块荒地,但荒地中一些位置存在杂物,对于一块不存在杂物的荒地,该荒地可以开垦当且仅当其上 下左右四个方向相邻的格子均不存在杂物｡
小杨可以选择至多一个位置,清除该位置的杂物,移除杂物后该位置变为荒地｡小杨想知道在清除至多一个位置的 杂物的情况下,最多能够开垦多少块荒地｡
输入格式
第一行包含两个正整数 $n$ , $m$ ,含义如题面所示｡
之后 行,每行包含一个长度为 且仅包含字符
对于全部数据,保证有 $1 \le n,m \le 1000$。
之后 行,每行包含一个长度为 且仅包含字符
. 和 # 的字符串｡如果为 . ,代表该位置为荒地,如果为 # , 代表该位置为杂物｡对于全部数据,保证有 $1 \le n,m \le 1000$。
输出格式
输出一个整数,代表在清除至多一个位置的杂物的情况下,最多能够开垦的荒地块数｡
输入输出样例
输入 #1
3 5 ..... .#..# .....
输出 #1
11
说明/提示
移除第二行从左数第二块空地的杂物后:
```
.....
....#
.....
```
第一行从左数前 $4$ 块荒地,第二行从左数前 $3$ 块荒地,第三行从左数前 $4$ 块荒地,均可开垦, $4+3+4=11$ 。
```
.....
....#
.....
```
第一行从左数前 $4$ 块荒地,第二行从左数前 $3$ 块荒地,第三行从左数前 $4$ 块荒地,均可开垦, $4+3+4=11$ 。