問題一覧 > 通常問題

No.157 2つの空洞

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 276
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
17 ProblemId : 233 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:21

問題文

壁'#'と空洞'.'からなる横の幅が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

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

########
#......#
#.####.#
#.####.#
#.######
########

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。