E - ブースの配置 Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

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

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

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

制約

  • 2\le H,W\le 8
  • H,W は整数
  • S_{i,j} は # または .
  • S_{i,j}= . を満たす (i,j) が 3 つ以上存在する

入力

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

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}

出力

答えを出力せよ。

入力例 1

3 3
#..
..#
#.#

出力例 1

2

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

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

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

入力例 2

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

出力例 2

0

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

入力例 3

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

出力例 3

41660