P8455 「SWTR-8」Minesweeper Counting

One day in June 2020, while waiting for the network to load, Little A opened Minesweeper, and from then on he could not stop. Little A is the kind of person who likes to do everything to the extreme, and playing games is no exception: he was willing to spend a huge amount of time trying again and again to break records. Night after night passed with skilled `Alt + G + N`. > “This run looks promising. I cleared the first fifty mines in less than forty-five seconds.” he thought, and his hand holding the mouse trembled slightly. > > “Hurry, hurry, hurry... only the last twenty mines left...”. > > At the crucial moment of the game, he could hardly hold back his excitement, until he met a 50-50 guess. > > He froze for a moment, then quickly clicked one of the last two empty cells. > > A white laser sweeping across the screen slowly passed by. He knew he had broken the record... by [a full twelve seconds](https://cdn.luogu.com.cn/upload/image_hosting/1seixkiz.png)! The huge surprise made him jump up. > > 2020.6.19

Below are simplified rules of Minesweeper: - Connectivity is defined as **8-connectivity**. - If you open a mine, all mines **explode simultaneously**, and the game ends. - If you open an empty cell and there are no mines around it, then recursively open the eight surrounding cells. - [As shown](https://cdn.luogu.com.cn/upload/image_hosting/kjjqs2v1.png), clicking any cell inside the red box can lead to the current situation. Given an initial map of size $n\times m$. Little A decides to enumerate all possible situations and find the best mouse clicking order to speedrun this map. To set a suitable array size, Little A needs to know how many different situations there are, modulo $998244353$. - If a cell is a mine, it has two states: exploded and not exploded. If a cell is empty, it has two states: opened and not opened. - Two situations are different if and only if there exists at least one cell whose state is different. - It is guaranteed that the empty cells with no surrounding mines form at most $37$ connected components.

The first line contains an integer $S$, representing the Subtask number of this test point. The second line contains two integers $n, m$. The next $n$ lines each contain a string of length $m$ describing the map, where $\texttt{.}$ means the cell has no mine, and $\texttt{*}$ means the cell has a mine.

Output one integer in one line, representing the answer.

**Sample Explanation** Use `.` to denote an unopened cell, `+` an opened cell, `*` an un-exploded mine, and `!` an exploded mine. All $4$ situations of Sample 1 are `.* +* .! +!`. All $20$ situations of Sample 2 are ```plain 0 ..* ... 1 ++* .+* ..! ..* ..* ++. ... ... .+. ..+ 2 ++! ++* .+! .+* .+* ..! ..! ..* ++. +++ ... .+. ..+ .+. ..+ .++ 3 ++! .+! .+! .+* ..! +++ .+. ..+ .++ .++ 4 .+! .++ ``` The numbers describe the minimum number of clicks. **Constraints and Notes** **This problem uses bundled testdata.** Let the empty cells with no surrounding mines form $d$ connected components. - Subtask #1 (15 points): $nm\leq 21$. - Subtask #2 (4 points): There is only one mine on the map. - 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$. Depends on Subtask #1, #2, #3, #4, #5. - Subtask #7 (9 points): $d \leq 23$. Depends on Subtask #6. - Subtask #8 (16 points): $d\leq 27$. Depends on Subtask #7. - Subtask #9 (17 points): $d\leq 33$. Depends on Subtask #8. - Subtask #10 (13 points): No special constraints. Depends on Subtask #9. For $100\%$ of the data: - $1\leq n, m\leq 500$. - $0\leq d\leq 37$. - It is **not guaranteed** that the map contains mines or empty cells. **Source** - [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). Thanks to [Elegia](https://www.luogu.com.cn/user/21423) for contributions to this problem. Translated by ChatGPT 5