Contest Duration: - (local time) (300 minutes) Back to Home
G - 村整備 /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

### 問題文

AtCoder 村は南北方向 N マス、東西方向 M マスの全部で N \times M 個のマスからなる長方形の形をしています。
いくつかのマスは壁であり、S_{i, j}# なら北から i 番目、西から j 番目のマスは壁であり、 . なら壁ではありません。
あなたは壁マスをちょうど 1 つ壁でないマスに変えます。以下の条件を満たすように変えるとき、変えるマスの候補はいくつあるかを求めてください。

• 壁でない 2 マスは全て、上下左右に 1 マス動くことを繰り返し AtCoder 村内の壁でないマスのみを通って互いに行き来可能である

### 制約

• 1 \le N \le 10
• 1 \le M \le 10
• N, M は整数
• S_i#. からなる長さ M の文字列 (1 \le i \le N)
• 壁マスと壁でないマスが少なくとも 1 つずつ存在する

### 入力

N M
S_1
S_2
S_3
\hspace{3pt} \vdots
S_N


### 入力例 1

3 3
..#
#..
.##


### 出力例 1

2


### 入力例 2

3 3
##.
##.
...


### 出力例 2

3


Score : 6 points

### Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

### Problem Statement

AtCoder Village is divided into a rectangular grid with N rows going east-west and M columns going north-south, for a total of N \times M squares. Some of the squares are "wall squares". If S_{i, j} is #, the square at the i-th row and j-th column is a wall square; if S_{i, j} is ., that square is not a wall square. You will change exactly one of the wall squares to a non-wall square. Find the number of wall squares that you can choose to change if the following condition must be satisfied after the change:

• For every pair of two non-wall squares, it is possible to travel between those squares by repeatedly moving one square up, down, left, or right, only passing through non-wall squares in the village.

### Constraints

• 1 \le N \le 10
• 1 \le M \le 10
• N and M are integers.
• S_i is a string of length M consisting of # and .. (1 \le i \le N)
• There is at least one wall square and at least one non-wall square.

### Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
S_3
\hspace{3pt} \vdots
S_N


### Output

Print the number of wall squares that you can choose to change to satisfy the condition.

### Sample Input 1

3 3
..#
#..
.##


### Sample Output 1

2


For example, if you change the square at the 2-nd row from the north and 1-st column from the west to a non-wall square, it will be possible to travel between every pair of non-wall squares. You can also choose the square at the 3-rd row from the north and 2-nd column from the west to satisfy the condition. There is no other such wall square, so the answer is 2.

### Sample Input 2

3 3
##.
##.
...


### Sample Output 2

3


Every wall square except the one at the north-west corner can be chosen to satisfy the condition. Note that it must be possible to travel between every pair of two non-wall squares, including the new non-wall square you make.