题目描述

我们有一个 $N$ 行 $M$ 列的网格，每个方格都被涂成黑色或白色。其中至少有一个方格被涂成黑色。
网格的初始状态由长度为 $M$ 的 $N$ 个字符串 $S_1,S_2,\ldots,S_N$ 给出。
如果 $S_i$ 的第 $j$ 个字符是 #，那么从上往下数第 $i$ 行第 $j$ 列的方格被涂成黑色；如果是 .，方格被涂成白色。

高滕想要将一些白色的方格（可能为零个）重新涂成黑色，以使涂成黑色的方格连通起来。找到他达到目标所需重新涂黑的方格的最小数量。

这里，当被涂成黑色的方格 $(S,T)$ 对来说是连通的，当且仅当对于每一对黑色的方格 $(S,T)$，存在正整数 $K$ 和一个黑色的方格序列 $X=(x_1,x_2,\ldots,x_K)$，满足 $x_1=S$，$x_K=T$ 并且对于每一个 $1\leq i\leq K-1$，$x_i$ 和 $x_{i+1}$ 相邻。
可以证明，在题目给定的约束条件下，高滕总能达到他的目标。

约束条件

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

输入

从标准输入读入数据，格式如下：

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

输出

打印高滕需要重新涂黑的方格的最小数量，使得涂成黑色的方格是连通的。

示例输入 1

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

示例输出 1

3

初始网格如下所示，其中 $(i,j)$ 表示从上往下数第 $i$ 行第 $j$ 列的方格。

假设高滕将三个方格 $(2,3),(2,4),(3,4)$（在下图中显示为红色）重新涂成黑色。

然后，我们得到以下方格涂成黑色的情况，包括一开始涂成黑色的方格。这些方格是连通的。

不可能重新涂黑两个或更少的方格使得方格连通，因此答案是 $3$。
注意，被涂成白色的方格不需要连通。

示例输入 2

3 3
###
###
###

示例输出 2

0

所有方格都可以一开始就被涂成黑色。

示例输入 3

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

示例输出 3

6