配点 : $600$ 点

問題文

$N$ 行 $M$ 列のマス目があり、各マスは黒または白で塗られています。 ここで、少なくとも $1$ つのマスが黒く塗られています。 最初のマス目の状態は $N$ 個の長さ $M$ の文字列 $S_1,S_2,\ldots,S_N$ で与えられます。 マス目の上から $i$ 行目 $(1\leq i\leq N)$ かつ左から $j$ 列目 $(1\leq j\leq M)$ のマスは、 $S_i$ の $j$ 文字目が # であるとき黒く、. であるとき白く塗られています。

高橋君の目標は白く塗られたいくつかのマス ($0$ 個でもよい ) を新しく黒く塗ることによって、黒く塗られたマス全体が 連結 になるようにすることです。 高橋君が目標を達成するために新しく塗る必要のあるマスの個数としてあり得る最小値を求めてください。

ただし、黒く塗られたマス全体が 連結 であるとは、黒く塗られたどの $2$ つのマスの組 $(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}$ が辺を共有しているようなものが存在することをいいます。 なお、問題の制約下でつねに、高橋君が目標を達成するような塗り方が存在することが証明できます。

制約

• $1 \leq N \leq 100$
• $1\leq M \leq 7$
• $N,M$ は整数
• $S_i$ は # と . のみからなる長さ $M$ の文字列
• 与えられるマス目において、黒く塗られたマスが $1$ つ以上存在する。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

出力

黒く塗られたマス全体が連結になるようにするために、新しく塗る必要のあるマスの個数としてあり得る最小値を出力せよ。

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

3

最初、マス目の状態は次のようになっています。ここで、上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ で表しています。

ここで、例えば、高橋君が $(2,3),(2,4),(3,4)$ の $3$ つのマス(下図の赤いマス)を新しく黒く塗ったとします。

このとき、最初から黒く塗られていたマスと新しく黒く塗られたマスは合わせて次のようになり、黒く塗られたマス全体は連結となります。

$2$ つ以下のマスを新しく黒く塗ることで黒く塗られたマス全体を連結にすることはできないため、$3$ が答えとなります。 白く塗られたマス全体を連結にする必要はないことに注意してください。

3 3
###
###
###

0

最初から全てのマスが黒く塗られている可能性もあります。

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

6