#GESP42. 荒地开垦
荒地开垦
题目描述:
小杨有一大片荒地,可以表示为一个 n 行 m 列的网格图。
小杨想要开垦这块荒地,但荒地中一些位置存在杂物,对于一块不存在杂物的荒地,该荒地可以开垦当且仅当其左上、左下、右上、右下四个方向相邻的格子均不存在杂物。
小杨可以选择至多一个位置,清除该位置的杂物,移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下,最多能够开垦多少块荒地。
输入格式:
- 第一行包含两个正整数 n, m,含义如题面所示。
- 之后 n 行,每行包含一个长度为 m 且仅包含字符 . 和 # 的字符串。如果为 .,则代表该位置为荒地;如果为 #,则代表该位置为杂物。
输出格式:
输出一个整数,代表在清除至多一个位置的杂物的情况下,最多能够开垦的荒地块数。
样例:
3 5
.....
.#..#
.....
12
样例说明:
用相同位置数值为 1 表示可以开垦的荒地,0 表示不能开垦:
0 1 0 0 1 1 0 1 1 0 0 1 0 0 1
共有 7 块荒地可以开垦。
移除第二行从左数第二块空地的杂物后:
1 1 1 0 1 1 1 1 1 0 1 1 1 0 1
有 7+5=12 块荒地可以开垦。
数据规模与约定:
对于全部数据,有 1 ≤ n, m ≤ 1000。