Description

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, 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.

Input Format

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 Format

Output one integer in one line, representing the answer.

0
1 2
.*

4

0
2 3
..*
...

20

0
4 4
..*.
.*..
*...
....

2112

0
7 6
..*...
......
*...**
......
..*...
......
......

5041530

Hint

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

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 D
• Idea & Solution: Alex_Wei.
• Tester: chenxia25 & asmend.

Thanks to Elegia for contributions to this problem.

Translated by ChatGPT 5