← 返回题目列表

AtCoder · highrate2025_e

E. 展位安排

中文机器翻译题面 查看原题

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