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

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

3 3
###
###
###

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

6

说明/提示

约束

• $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 翻译