#B4167. [GXPC-S 2024] 扫雷
[GXPC-S 2024] 扫雷
题目背景
小林最近迷上了扫雷游戏。
题目描述
一个扫雷游戏可以被抽象成一个 行 列的字符矩阵,不妨记第 行第 列的字符为 。
若 ,表示格子 上有一个地雷;
若 ,表示格子 情况未知;
若 ,表示格子 周围的 个格子中有 个地雷(这个格子本身没有地雷)。 形式化地说,记
$$f(i,j)=\begin{cases} 1, & (i,j)\text{ 上有地雷} \\ 0, & \text{其他情况} \\ \end{cases} $$特别地,对于超出棋盘边界的情况,规定 。 则 $\displaystyle S_{i,j}=\sum_{p=-1}^1\sum_{q=-1}^1 f(i+p,j+q)$。
给定一个棋盘,你可以任意决定每个 格子上是否有炸弹。你想要知道是否存在方案使得这个棋盘是合法的。 我们定义一个棋盘合法,当且仅当填有数字 的格子周围的八个格子上恰好有 个炸弹。
你需要解决 组数据。
输入格式
本题单个测试点内含多组测试数据。
第一行,一个正整数 ,代表数据组数;
对于每组数据,输入 行:
- 第一行,两个正整数 ,描述棋盘的行数和列数;
- 接下来 行,第 行的第 个字符描述 。
输出格式
对于每组数据,输出一行。
若存在合法的方案,输出 YES
;否则输出 NO
。
3
2 2
**
2?
2 2
*1
3?
2 2
**
21
YES
NO
NO
提示
对于第一组数据:问号处选择不填是一种合法方案。可以证明这是唯一的合法方案。
本题采用捆绑测试。
- Subtask 1(20pts):至多存在 组 ,使得 ;
- Subtask 2(80pts):无额外约束。
对于 的数据,保证:
- ;
- 至多存在 组 ,使得 ;
- ,保证 $S_{i,j}\in\{0,1,2,3,4,5,6,7,8,\texttt{?},\texttt{*}\}$。