「SWTR-8」扫雷计数
题目背景
2020 年 6 月的某一天，小 A 在等待网络加载的过程中打开了扫雷，从此便一发不可收拾。
小 A 是一个任何事都喜欢做到极致的人，玩游戏也不例外：他不惜花费大量时间不断尝试打破记录。一个个夜晚就在熟练的 `Alt + G + N` 中过去了。
> “这把有戏，前五十个雷只用了不到四十五秒”。他心里想着，紧握鼠标的手微微颤抖。
>
> “快，快，快 …… 还有最后二十个雷 ……”。
>
> 游戏的关键时刻，他难以按捺激动的心情。直到他遇到了二选一。
>
> 他愣了一下，随后迅速按下最后两块空地当中的一个。
>
> 一束横贯屏幕的白色激光缓缓扫过，他知道自己打破了记录 …… [整整十二秒](https://cdn.luogu.com.cn/upload/image_hosting/1seixkiz.png)！巨大的惊喜让他跳了起来。
>
> 2020.6.19
题目描述
以下是简化后的扫雷游戏规则：
- 定义连通为 **八连通**。
- 如果打开雷，所有雷 **全部同时爆炸**，游戏结束。
- 如果打开空地，若其周围没有雷，则递归打开周围八个方块。
- [如图](https://cdn.luogu.com.cn/upload/image_hosting/kjjqs2v1.png)，点开任意红色框内方块均形成当前局面。
给定一张 $n\times m$ 的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。
为设置合适的数组大小，小 A 需要知道有多少种不同局面。对 $998244353$ 取模。
- 如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。
- 两个局面不同，当且仅当存在方块状态不同。
- 保证周围无雷的空地形成不超过 $37$ 个连通块。
输入输出格式
输入格式
第一行一个整数 $S$，表示该测试点的 Subtask 编号。
第二行两个整数 $n, m$。
接下来 $n$ 行，每行一个长度为 $m$ 的字符串描述地图，其中 $\texttt{.}$ 表示方块无雷，$\texttt{*}$ 表示方块有雷。
输出格式
一行一个整数表示答案。
输入输出样例
输入样例 #1
0
1 2
.*输出样例 #1
4输入样例 #2
0
2 3
..*
...输出样例 #2
20输入样例 #3
0
4 4
..*.
.*..
*...
....输出样例 #3
2112输入样例 #4
0
7 6
..*...
......
*...**
......
..*...
......
......输出样例 #4
5041530说明
**「样例解释」**
用 `.` 表示未打开的方块，`+` 表示打开的方块，`*` 表示未爆炸的雷，`!` 表示爆炸的雷。
样例 1 的所有 4 种局面为 `.* +* .! +!`。
样例 2 的所有 20 种局面为
```plain
0
..*
...
1
++* .+* ..! ..* ..*
++. ... ... .+. ..+
2
++! ++* .+! .+* .+* ..! ..! ..*
++. +++ ... .+. ..+ .+. ..+ .++
3
++! .+! .+! .+* ..!
+++ .+. ..+ .++ .++
4
.+!
.++
```
数字描述了最少点击次数。
**「数据范围与约定」**
**本题采用捆绑测试。**
设周围无雷的空地形成 $d$ 个连通块。
- Subtask #1（15 points）：$nm\leq 21$。
- Subtask #2（4 points）：地图中只有一个雷。
- Subtask #3（5 points）：$d = 0$。
- Subtask #4（6 points）：$d = 1$。
- Subtask #5（7 points）：$d = 2$。
- Subtask #6（8 points）：$d \leq 17$。依赖 Subtask #1，#2，#3，#4，#5。
- Subtask #7（9 points）：$d \leq 23$。依赖 Subtask #6。
- Subtask #8（16 points）：$d\leq 27$。依赖 Subtask #7。
- Subtask #9（17 points）：$d\leq 33$。依赖 Subtask #8。
- Subtask #10（13 points）：无特殊限制。依赖 Subtask #9。
对于 $100\%$ 的数据：
- $1\leq n, m\leq 500$。
- $0\leq d\leq 37$。
- **不保证** 地图中有雷或空地。
**「题目来源」**
- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) D
- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。
- Tester：[chenxia25](https://www.luogu.com.cn/user/138400) & [asmend](https://www.luogu.com.cn/user/21658)。
感谢 [Elegia](https://www.luogu.com.cn/user/21423) 对本题做出的贡献。