配点 : 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