Contest Duration: - (local time) (120 minutes) Back to Home
D - Skate /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 高橋くんがマス (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


.........
........#
.........


### 入力例 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