問題一覧 > 通常問題

No.157 2つの空洞

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

問題文

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

入力

W H
C0,0C1,0...CW−1,0
C0,1C1,1...CW−1,1
…
C0,H−1C1,H−1...CW−1,H−1

Wは横幅,Hは縦幅をあらわす。W,Hはともに整数。（1≤W,H≤20）
Cxyはその位置が壁があるか空洞かをあらわす。
壁は'#'であらわされ、空洞は'.'であらわされる。
空洞は縦か横に接しているとつながっているとし、斜めではつながらない。
空洞のかたまりはちょうど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もしくは右上の雲マークをクリックしてアカウントを作成してください。