G - 村整備 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、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 個目、西から 1 個目のマスを壁でないマスにすると、全ての壁でないマスが壁を通らずに互いに行き来可能になります。
北から 3 個目、西から 2 個目のマスも条件を満たします。それ以外の壁マスは条件を満たさないので答えは 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.