E - ブースの配置

E - ブースの配置解説

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 400 点

H \times W のグリッドで表される会場があります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。マス (i,j) には S_{i,j} が # ならば壁があり、 . ならば空であり通行可能です。

あなたはこの会場の空のマスを 3 マス選んでブースを設置します。以下の条件を満たすようなブースの設置方法は何通りあるか求めてください。ただし、ブース同士は区別しないものとします。

以下を両方満たすようなマス (r,c) が存在する。
- マス (r,c) には壁もブースもない。
- 全てのブースについて、マス (r,c) から上下左右に隣接する壁もブースもないマスに移動する操作を 0 回以上繰り返すことでそのブースに上下左右に隣接するマスに到達することができる。

入力は以下の形式で標準入力から与えられる。

H W
S_{1,1}S_{1,2}\ldots S_{1,W}
S_{2,1}S_{2,2}\ldots S_{2,W}
\vdots
S_{H,1}S_{H,2}\ldots S_{H,W}

答えを出力せよ。

3 3
#..
..#
#.#

以下の 2 つの配置が条件を満たします。ただし、ブースがあるマスは B で表しています。

#B. #.B
B.# B.#
#B# #B#

どちらの配置もマス (2,2) から全てのブースに到達可能です。

3 5
.....
.###.
.....

条件を満たすブースの配置方法は存在しません。したがって、 0 を出力してください。

8 8
........
........
........
........
........
........
........
........