题目描述
Background
On a day in June 2020, while waiting for the internet to load, Little A opened Minesweeper and became utterly engrossed.
Little A is someone who strives for perfection in everything, and this extends to gaming: he spends considerable time trying to break records. Nights pass by as he熟练地 presses Alt + G + N.
"This game is promising, I've cleared the first fifty mines in under forty-five seconds," he thinks to himself, his hand gripping the mouse slightly trembling.
"Quick, quick, quick... only twenty mines left..."
At the critical moment of the game, he can hardly contain his excitement. Until he faces a binary choice.
He pauses for a moment, then quickly clicks one of the last two empty squares.
A beam of white laser slowly sweeps across the screen, and he knows he has broken the record... a full twelve seconds! The immense joy makes him jump up.
June 19, 2020
Problem Description
Here are the simplified rules of Minesweeper:
- Define connectivity as eight-connected.
- If a mine is clicked, all mines explode simultaneously, ending the game.
- If an empty square is clicked and it has no surrounding mines, recursively open the surrounding eight squares.
- As shown in the figure, clicking any square within the red frame results in the current situation.
Given an initial map of size $n \times m$. Little A decides to search for all possible situations and find the optimal mouse click sequence to speedrun this map.
To set an appropriate array size, Little A needs to know how many different situations there are, modulo $998244353$.
- If a square is a mine, it has two states: exploded and unexploded; if a square is empty, it has two states: opened and unopened.
- Two situations are different if and only if there is a square with a different state.
- Ensure that empty squares with no surrounding mines form no more than $37$ connected components.
Input Format
The first line contains an integer $S$, indicating the Subtask number for this test point.
The second line contains two integers $n, m$.
The next $n$ lines, each containing a string of length $m$, describe the map, where . denotes a square without a mine and * denotes a square with a mine.
Output Format
A single line containing an integer representing the answer.
Sample Input and Output
Sample Input #1
0
1 2
.*
Sample Output #1
4
Sample Input #2
0
2 3
..*
...
Sample Output #2
20
Sample Input #3
0
4 4
..*.
.*..
*...
....
Sample Output #3
2112
Sample Input #4
0
7 6
..*...
......
*...**
......
..*...
......
......
Sample Output #4
5041530
Notes
Sample Explanation
Use . to represent an unopened square, + to represent an opened square, * to represent an unexploded mine, and ! to represent an exploded mine.
All 4 situations for Sample 1 are .* +* .! +!.
All 20 situations for Sample 2 are:
0
..*
...
1
++* .+* ..! ..* ..*
++. ... ... .+. ..+
2
++! ++* .+! .+* .+* ..! ..! ..*
++. +++ ... .+. ..+ .+. ..+ .++
3
++! .+! .+! .+* ..!
+++ .+. ..+ .++ .++
4
.+!
.++
The numbers describe the minimum number of clicks.
Data Range and Constraints
This problem is bundled with subtasks.
Let $d$ be the number of connected components of empty squares with no surrounding mines.
- Subtask #1 (15 points): $\leq 21$.
- Subtask #2 (4 points): There is only one mine in 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 restrictions. 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 squares.
Source
- Sweet Round 8 D
- Idea & Solution: Alex_Wei.
- Tester: chenxia25 & asmend.
Thanks to Elegia for their contribution to this problem.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分