No.157 2つの空洞

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 207
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
13 ProblemId : 233 / 出題時の順位表

問題文

壁'#'と空洞'.'からなる横の幅がW、縦の幅がHの空間がある。
調べたところ壁の中に空洞のかたまりが2つあることがわかった。
壁'#'をいくつかどけることで2つの空洞のかたまりをつなげたい。
最小でいくつの壁'#'をどければ良いかを答えよ。

入力

$W\ H$
$C_{0,0}C_{1,0}...C_{W-1,0}$
$C_{0,1}C_{1,1}...C_{W-1,1}$
$\dots$
$C_{0,H-1}C_{1,H-1}...C_{W-1,H-1}$

$W$は横幅,$H$は縦幅をあらわす。$W,H$はともに整数。($1 \le W, H \le 20 $)
$C_{x y}$はその位置が壁があるか空洞かをあらわす。
壁は'#'であらわされ、空洞は'.'であらわされる。
空洞は縦か横に接しているとつながっているとし、斜めではつながらない。
空洞のかたまりはちょうど2つあることが保証される。
また、空洞のかたまりはかならず壁'#'で囲われることが保証される。

出力

どける必要のある壁の最小の数を1行で答えよ。
最後に改行してください。

サンプル

サンプル1
入力
9 5
#########
#.####.##
#..###.##
#..###..#
#########
出力
3

左と右に空洞のかたまりが1つずつある。
次のように壁を3つどければ2つの空洞はつながる。

#########
#.####.##
#......##
#..###..#
#########
サンプル2
入力
8 5
########
####..##
#..#..##
#...####
########
出力
1

次のように壁を1つどければ2つの空洞はつながる。

########
####..##
#.....##
#...####
########
サンプル3
入力
9 9
#########
#.......#
#.#####.#
#.#...#.#
#.#.#.#.#
#.#...#.#
#.#####.#
#.......#
#########
出力
1

このような図も2つの空洞とみなします。
例えば次のように空洞をつなげることができます。

#########
#.......#
#.#####.#
#.#...#.#
#...#.#.#
#.#...#.#
#.#####.#
#.......#
#########
サンプル4
入力
8 6
########
#....###
#.######
#.####.#
#.######
########
出力
3

つぎのように空洞をつなげます。

########
#......#
#.####.#
#.####.#
#.######
########
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。