分数: 600 点
问题陈述
我们有一个网格 N 行和 M 列,其中每个方块都漆成黑色或白色。
在这里,至少有一个方块被漆成黑色。
网格的初始状态为 N 字符串 S_1,S_2,\ldots,S_N 长度 M.
广场 i从顶部开始的第行和 j如果从左边算起第 1 列被涂成黑色 j- 第一个字符 S_i is #,如果是白色 ..
Takahashi 想要将一些白色方块(可能为零)重新涂成黑色,以便涂成黑色的方块 已连接。 求他需要的最少格子数 重新喷漆 实现他的目标。
这里,漆成黑色的方块据说是 已连接 当,对于每对方块 (S,T) 涂成黑色,有一个正整数 K 和一系列 K 方块 X=(x_1,x_2,\ldots,x_K) 涂成黑色,这样 x_1=S, x_K=T,和 x_i 和 x_{i+1} 为每个人分享一边 1\leq i\leq K-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