No.157 Two Cavities
タグ : / 解いたユーザー数 298
作問者 :
nmnmnmnmnmnmnm
Problem Statement
There is a space of width W and height H consisting of walls '#' and cavities '.'.
An investigation has revealed that there are 2 clusters of cavities inside the walls.
You want to connect the 2 clusters of cavities by removing some walls '#'.
Find the minimum number of walls '#' that must be removed.
Input
$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$ denotes the width and $H$ denotes the height. $W,H$ are both integers. ($1 \le W, H \le 20 $)
$C_{x y}$ denotes whether that position is a wall or a cavity.
A wall is represented by '#', and a cavity is represented by '.'.
Cavities are connected if they are adjacent vertically or horizontally; they are not connected diagonally.
It is guaranteed that there are exactly 2 clusters of cavities.
It is also guaranteed that the clusters of cavities are always surrounded by walls '#'.
Output
Output the minimum number of walls that need to be removed on one line.
Print a newline at the end.
Sample
Sample 1
Input
9 5 ######### #.####.## #..###.## #..###..# #########
Output
3
There is one cluster of cavities on the left and one on the right.
Removing 3 walls as follows connects the 2 cavities.
######### #.####.## #......## #..###..# #########
Sample 2
Input
8 5 ######## ####..## #..#..## #...#### ########
Output
1
Removing 1 wall as follows connects the 2 cavities.
######## ####..## #.....## #...#### ########
Sample 3
Input
9 9 ######### #.......# #.#####.# #.#...#.# #.#.#.#.# #.#...#.# #.#####.# #.......# #########
Output
1
A figure like this is also regarded as 2 cavities.
For example, the cavities can be connected as follows.
######### #.......# #.#####.# #.#...#.# #...#.#.# #.#...#.# #.#####.# #.......# #########
Sample 4
Input
8 6 ######## #....### #.###### #.####.# #.###### ########
Output
3
Connect the cavities as follows.
######## #......# #.####.# #.####.# #.###### ########
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。