AT_highrate2025_e ブースの配置

有一个由 $H \times W$ 的网格表示的会场。从上到下的第 $i$ 行，从左到右的第 $j$ 列的格子记作 $(i,j)$。如果 $S_{i,j}$ 是 `#`，则该格子为墙；如果是 `.`，则该格子为空地，可以通行。 你要在会场的空地格子中选择 $3$ 个格子设置展位。请计算有多少种设置展位的方法满足下列条件。需要注意的是，展位彼此之间没有区别。 - 存在一个格子 $(r,c)$，同时满足如下条件： - 格子 $(r,c)$ 既不是墙，也没有展位。 - 对于每一个展位，都存在从格子 $(r,c)$ 出发，经过若干次移动到上下左右相邻且既不是墙也没有展位的格子，最终能够到达该展位上下左右相邻的格子的位置（可以重复经过格子或者不移动）。

输入从标准输入按以下格式给出。 > $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 有如下 $2$ 种配置满足条件。展位所在的格子用 `B` 表示。 ``` #B. #.B B.# B.# #B# #B# ``` 在这两种配置下，从格子 $(2,2)$ 出发，都可以到达所有展位相邻的格子。 ## 样例解释 2 不存在满足条件的展位配置方式。因此，请输出 $0$。 ## 数据范围 - $2\le H,W\le 8$ - $H,W$ 均为整数 - $S_{i,j}$ 仅为 `#` 或 `.` - 满足 $S_{i,j} = . $ 的格子数量不少于 $3$。 由 ChatGPT 5 翻译