当前没有测试数据。

ex - 统一

得分：600 分

题目描述

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

高桥想要重新涂一些白色方格为黑色，使得被涂成黑色的方格连通。 求他为了实现该目标至少需要重新涂多少个方格。

这里，被涂成黑色的方格被称为连通，当且仅当，对于每一对被涂成黑色的方格 $(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$

输出

输出高桥为使被涂成黑色的方格连通而需要重新涂的方格的最小数量。

---

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

3

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

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

那么，包括初始被涂成黑色的方格在内，以下方格被涂成黑色并且连通。

无法重新涂少于二个方格使得被涂成黑色的方格连通，所以答案是 $3$。
注意，被涂成白色的方格没有必要连通。

---

3 3
###
###
###

0

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

---

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

6