AT_abc296_h [ABC296Ex] Unite

有一个 $N$ 行 $M$ 列的格子，每个格子被涂成黑色或白色。已知至少有一个格子是黑色的。 初始格子的状态由 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\ldots,S_N$ 给出。 从上到下第 $i$ 行、从左到右第 $j$ 列的格子，如果 $S_i$ 的第 $j$ 个字符为 `#`，则该格子为黑色；如果为 `.`，则为白色。 高桥君的目标是通过将若干（可以为 $0$ 个）白色格子重新涂成黑色，使得所有黑色格子**连通**。请你求出，为了达成目标，最少需要重新涂黑的格子数。 这里，所有黑色格子连通的定义是：对于任意两个黑色格子 $S$ 和 $T$，存在一个正整数 $K$ 和长度为 $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}$ 共享一条边。 在本题的约束下，总是存在一种方案可以使高桥君达成目标。

输入按以下格式从标准输入读入。 > $N$ $M$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

输出为了使所有黑色格子连通，最少需要重新涂黑的格子数。

## 约束 - $1 \leq N \leq 100$ - $1 \leq M \leq 7$ - $N,M$ 均为整数 - $S_i$ 仅由 `#` 和 `.` 组成，长度为 $M$ - 输入的格子中至少有一个格子是黑色 ## 样例解释 1 初始时，格子的状态如下。这里，从上到下第 $i$ 行、从左到右第 $j$ 列的格子记作 $(i,j)$。  例如，高桥君可以将 $(2,3),(2,4),(3,4)$ 这三个格子（下图红色格子）重新涂成黑色。  此时，原本的黑色格子和新涂黑的格子合起来如下，所有黑色格子连通。  无法通过重新涂黑 $2$ 个或更少的格子使所有黑色格子连通，因此答案为 $3$。 注意，不需要使所有白色格子连通。 ## 样例解释 2 也有可能一开始所有格子都是黑色。 由 ChatGPT 4.1 翻译