/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋くんは H 行 W 列のマスからなるスケートリンクにいます。
北から r 行目、西から c 列目をマス (r, c) と表すことにします。
各マスは氷または地面であり、マス (r, c) は S_{r, c} が # であるときは地面、. であるときは氷です。
スケートリンクの外側は壁で覆われています。
高橋くんは、スケートリンク上で静止しているとき、東西南北のいずれかに移動を開始することができます。 移動開始後、高橋くんは同じ方向に動き続け、壁にぶつかるか、（移動を開始したマス以外の）地面のマスの 上 にたどりついたときに静止します。
以下の条件を満たす時、「 マス (r, c) から見て、スケートリンクは無駄がない」と言います:
- 高橋くんがマス (r, c) で静止している状態から、うまく移動を繰り返すことによって、全てのマスを 通過 することができる。（各マスの上で静止できるかどうかは問わない。）
高橋くんはどのマスから見てもスケートリンクに無駄がないようにするために、いくつかの氷のマスを地面のマスに変更したいです。 最小でいくつのマスを変更すればよいか求めてください。
制約
- 2\le H,W \le 1000
- S_{r,c} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}\dots S_{1,W}
\vdots
S_{H,1}\dots S_{H,W}
出力
どのマスから見てもスケートリンクに無駄がないようにするために変更する必要のあるマスの数の最小値を出力せよ。
入力例 1
3 9 ......... ......... .........
出力例 1
1
最初の状態では、マス (1,1) から始めてマス (2,2) を通過することができません。 例えば以下のように変更すれば条件を満たせます。
......... ........# .........
入力例 2
10 10 .......... #...#..... .......... .......... .......... ....#..... .#......#. .......... .......... ..........
出力例 2
6
Score : 600 points
Problem Statement
Takahashi is on a skating rink consisting of H rows and W columns of squares.
Let (r, c) denote the square at the r-th row from the north and c-th column from the west.
Each square is ice or ground; (r, c) is ground if S_{r, c} is # and ice if S_{r, c} is ..
There are walls around the rink.
When Takahashi is standing still on the rink, he can start moving to the east, west, south, or north. After he starts moving, he will keep moving in the same direction, until he bumps into a wall or he is on a ground square (other than the square where he started moving).
We say the rink is efficient for (r, c) when the following condition is satisfied:
- There is a sequence of moves that starts at (r, c), standing still, and passes every square. (It is not required to stop on each square.)
Takahashi wants to change some number of ice squares to ground squares so that the rink is efficient for every square. How many squares does he need to change, at least?
Constraints
- 2\le H,W \le 1000
- S_{r,c} is
#or..
Input
Input is given from Standard Input in the following format:
H W
S_{1,1}\dots S_{1,W}
\vdots
S_{H,1}\dots S_{H,W}
Output
Print the minimum number of changes needed to make the rink efficient for every square.
Sample Input 1
3 9 ......... ......... .........
Sample Output 1
1
Initially, it is impossible to start at (1, 1) and pass (2, 2). One way to meet the objective is to change the rink as follows:
......... ........# .........
Sample Input 2
10 10 .......... #...#..... .......... .......... .......... ....#..... .#......#. .......... .......... ..........
Sample Output 2
6