A5024 | $减少荒地开垦$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小明有一大片荒地，可以表示为一个 $n$ 行 $m$ 列的网格图。 现在到了开荒种地的季节，荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。 小明需要把整片地里所有可以被开垦的荒地全都开垦一遍，但是小明由于时间问题希望可以开垦尽量少的荒地，决定在地图上的某个位置增加一个新的杂物。请问在增加杂物之后， 需要小明开垦的最少荒地数量是多少？

第一行包含两个正整数 $n, m$。 $(1 \leq n, m \leq 1000)$ 之后 $n$ 行，每行包含一个长度为 $m$ 且仅包含字符 . 和 # 的字符串。如果为 .，代表该位置为荒地；如果为 #，代表该位置为杂物。

输出一个整数，代表在增加至多一个位置的杂物的情况下，最少能够开垦的荒地数量。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出