AT_past202010_g 村整備

[problemUrl]: https://atcoder.jp/contests/past202010-open/tasks/past202010_g AtCoder 村は南北方向 $ N $ マス、東西方向 $ M $ マスの全部で $ N\ \times\ M $ 個のマスからなる長方形の形をしています。 いくつかのマスは壁であり、$ S_{i,\ j} $ が `#` なら北から $ i $ 番目、西から $ j $ 番目のマスは壁であり、 `.` なら壁ではありません。 あなたは壁マスをちょうど $ 1 $ つ壁でないマスに変えます。以下の条件を満たすように変えるとき、変えるマスの候補はいくつあるかを求めてください。 - 壁でない $ 2 $ マスは全て、上下左右に $ 1 $ マス動くことを繰り返し AtCoder 村内の壁でないマスのみを通って互いに行き来可能である

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S_1 $ $ S_2 $ $ S_3 $ $ \hspace{3pt}\ \vdots $ $ S_N $

条件を満たす、壁でないマスに変えるマスの候補の数を出力せよ。

### 注意 この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \le\ N\ \le\ 10 $ - $ 1\ \le\ M\ \le\ 10 $ - $ N,\ M $ は整数 - $ S_i $ は `#` と `.` からなる長さ $ M $ の文字列 $ (1\ \le\ i\ \le\ N) $ - 壁マスと壁でないマスが少なくとも $ 1 $ つずつ存在する ### Sample Explanation 1 例えば北から $ 2 $ 個目、西から $ 1 $ 個目のマスを壁でないマスにすると、全ての壁でないマスが壁を通らずに互いに行き来可能になります。 北から $ 3 $ 個目、西から $ 2 $ 個目のマスも条件を満たします。それ以外の壁マスは条件を満たさないので答えは $ 2 $ です。 ### Sample Explanation 2 一番北西のマスを除く全ての壁マスが条件を満たします。 新たにできた壁でないマスも含めて全ての壁でないマスが行き来可能でならなければならないことに注意してください。