连通

题目描述

我们有一个 $N$ 行 $M$ 列的网格，每个方格被涂成黑色或白色。 这里，至少有一个方格被涂成黑色。

网格的初始状态由 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\ldots,S_N$ 给出。

如果 $S_i$ 的第 $j$ 个字符是 #，则从上数第 $i$ 行、从左数第 $j$ 列的方格是黑色；如果是 .，则为白色。

高桥想把一些白色方格（也可以为 0 个）重新涂成黑色，使得黑色方格连成一片。 求为了达成目标最少需要重新涂黑的格子数。

这里，当且仅当对每一对涂黑的方格 $(S,T)$，都存在一个正整数 $K$ 和一个由涂黑方格组成的序列 $X=(x_1,x_2,\ldots,x_K)$，满足 $x_1=S$，$x_K=T$，且对每个 $1\le i\le K-1$，$x_i$ 和 $x_{i+1}$ 共有一条边时，称涂黑的方格是连通的。

可以证明，在本题的约束下，高桥总是有办法达成目标。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出为了让黑色方格连成一片，高桥最少需要重新涂黑的格子数。

样例

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

3

其中 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的方格。

假设高桥把三个方格 $(2,3),(2,4),(3,4)$ 重新涂成黑色。

那么，包括一开始就是黑色的方格在内，得到的黑色方格是连通的。

要让黑色方格连通，不可能只重新涂黑两个或更少的方格，因此答案是 $3$。

注意白色方格不需要连通。

3 3
###
###
###

0

所有方格可能一开始就是黑色的。

10 1
.
#
.
.
.
.
.
.
#
.

6

数据范围

• $1 \le N \le 100$
• $1 \le M \le 7$
• $N$ 和 $M$ 是整数。
• $S_i$ 是由 # 和 . 组成的长度为 $M$ 的字符串。
• 给定的网格中至少有一个方格被涂成黑色。