Background

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! The huge surprise made him jump up.

2020.6.19

Problem 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