/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 行 M 列のマス目があり、各マスは黒または白で塗られています。
ここで、少なくとも 1 つのマスが黒く塗られています。
最初のマス目の状態は N 個の長さ M の文字列 S_1,S_2,\ldots,S_N で与えられます。
マス目の上から i 行目 (1\leq i\leq N) かつ左から j 列目 (1\leq j\leq M) のマスは、
S_i の j 文字目が # であるとき黒く、. であるとき白く塗られています。
高橋君の目標は白く塗られたいくつかのマス (0 個でもよい ) を新しく黒く塗ることによって、黒く塗られたマス全体が 連結 になるようにすることです。 高橋君が目標を達成するために新しく塗る必要のあるマスの個数としてあり得る最小値を求めてください。
ただし、黒く塗られたマス全体が 連結 であるとは、黒く塗られたどの 2 つのマスの組 (S,T) についても、
正整数 K と長さ K の黒く塗られたマスの列 X=(x_1,x_2,\ldots,x_K) であって、x_1=S, x_K=T
かつ任意の 1\leq i\leq K-1 について x_i と x_{i+1} が辺を共有しているようなものが存在することをいいます。
なお、問題の制約下でつねに、高橋君が目標を達成するような塗り方が存在することが証明できます。
制約
- 1 \leq N \leq 100
- 1\leq M \leq 7
- N,M は整数
- S_i は
#と.のみからなる長さ M の文字列 - 与えられるマス目において、黒く塗られたマスが 1 つ以上存在する。
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
黒く塗られたマス全体が連結になるようにするために、新しく塗る必要のあるマスの個数としてあり得る最小値を出力せよ。
入力例 1
3 5 ...#. .#... ....#
出力例 1
3
最初、マス目の状態は次のようになっています。ここで、上から i 行目、左から j 列目のマスを (i,j) で表しています。
ここで、例えば、高橋君が (2,3),(2,4),(3,4) の 3 つのマス(下図の赤いマス)を新しく黒く塗ったとします。
このとき、最初から黒く塗られていたマスと新しく黒く塗られたマスは合わせて次のようになり、黒く塗られたマス全体は連結となります。
2 つ以下のマスを新しく黒く塗ることで黒く塗られたマス全体を連結にすることはできないため、3 が答えとなります。
白く塗られたマス全体を連結にする必要はないことに注意してください。
入力例 2
3 3 ### ### ###
出力例 2
0
最初から全てのマスが黒く塗られている可能性もあります。
入力例 3
10 1 . # . . . . . . # .
出力例 3
6
Score : 600 points
Problem Statement
We have a grid with N rows and M columns, where each square is painted black or white.
Here, at least one square is painted black.
The initial state of the grid is given as N strings S_1,S_2,\ldots,S_N of length M.
The square at the i-th row from the top and j-th column from the left is painted black if the j-th character of S_i is #, and white if it is ..
Takahashi wants to repaint some white squares (possibly zero) black so that the squares painted black are connected. Find the minimum number of squares he needs to repaint to achieve his objective.
Here, the squares painted black are said to be connected when, for every pair of squares (S,T) painted black, there are a positive integer K and a sequence of K squares X=(x_1,x_2,\ldots,x_K) painted black such that x_1=S, x_K=T, and x_i and x_{i+1} share a side for every 1\leq i\leq K-1.
It can be proved that, under the constraints of the problem, there is always a way for Takahashi to achieve his objective.
Constraints
- 1 \leq N \leq 100
- 1\leq M \leq 7
- N and M are integers.
- S_i is a string of length M consisting of
#and.. - The given grid has at least one square painted black.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print the minimum number of squares that Takahashi needs to repaint for the squares painted black to be connected.
Sample Input 1
3 5 ...#. .#... ....#
Sample Output 1
3
The initial grid looks as follows, where (i,j) denotes the square at the i-th row from the top and j-th column from the left.
Assume that Takahashi repaints three squares (2,3),(2,4),(3,4) (shown red in the figure below) black.
Then, we have the following squares painted black, including the ones painted black from the beginning. These squares are connected.
It is impossible to repaint two or fewer squares black so that the squares painted black are connected, so the answer is 3.
Note that the squares painted white do not have to be connected.
Sample Input 2
3 3 ### ### ###
Sample Output 2
0
All squares might be painted black from the beginning.
Sample Input 3
10 1 . # . . . . . . # .
Sample Output 3
6