← 返回题目列表

AtCoder · abc296_h

Ex. 团结起来

中文机器翻译题面 查看原题

分数: 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