「SWTR-8」扫雷计数

以下是简化后的扫雷游戏规则： - 定义连通为 **八连通**。 - 如果打开雷，所有雷 **全部同时爆炸**，游戏结束。 - 如果打开空地，若其周围没有雷，则递归打开周围八个方块。 - [如图](https://cdn.luogu.com.cn/upload/image_hosting/kjjqs2v1.png)，点开任意红色框内方块均形成当前局面。 给定一张 $n\times m$ 的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。 为设置合适的数组大小，小 A 需要知道有多少种不同局面。对 $998244353$ 取模。 - 如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。 - 两个局面不同，当且仅当存在方块状态不同。 - 保证周围无雷的空地形成不超过 $37$ 个连通块。 ## Input 第一行一个整数 $S$，表示该测试点的 Subtask 编号。 第二行两个整数 $n, m$。 接下来 $n$ 行，每行一个长度为 $m$ 的字符串描述地图，其中 $\texttt{.}$ 表示方块无雷，$\texttt{*}$ 表示方块有雷。 ## Output 一行一个整数表示答案。 [samples] ## Background 2020 年 6 月的某一天，小 A 在等待网络加载的过程中打开了扫雷，从此便一发不可收拾。 小 A 是一个任何事都喜欢做到极致的人，玩游戏也不例外：他不惜花费大量时间不断尝试打破记录。一个个夜晚就在熟练的 `Alt + G + N` 中过去了。 > “这把有戏，前五十个雷只用了不到四十五秒”。他心里想着，紧握鼠标的手微微颤抖。 > > “快，快，快 …… 还有最后二十个雷 ……”。 > > 游戏的关键时刻，他难以按捺激动的心情。直到他遇到了二选一。 > > 他愣了一下，随后迅速按下最后两块空地当中的一个。 > > 一束横贯屏幕的白色激光缓缓扫过，他知道自己打破了记录 …… [整整十二秒](https://cdn.luogu.com.cn/upload/image_hosting/1seixkiz.png)！巨大的惊喜让他跳了起来。 > > 2020.6.19 ## Note **「样例解释」** 用 `.` 表示未打开的方块，`+` 表示打开的方块，`*` 表示未爆炸的雷，`!` 表示爆炸的雷。 样例 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) 对本题做出的贡献。