No.157 2つの空洞
nmnmnmnmnmnmnm問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。