#B4167. [GXPC-S 2024] 扫雷

[GXPC-S 2024] 扫雷

题目背景

小林最近迷上了扫雷游戏。

题目描述

一个扫雷游戏可以被抽象成一个 nnmm 列的字符矩阵,不妨记第 ii 行第 jj 列的字符为 Si,jS_{i,j}

Si,j=*S_{i,j}=\texttt{*},表示格子 (i,j)(i,j) 上有一个地雷;

Si,j=?S_{i,j}=\texttt{?},表示格子 (i,j)(i,j) 情况未知;

Si,j[0,8]S_{i,j}\in [0,8],表示格子 (i,j)(i,j) 周围的 88 个格子中有 Si,jS_{i,j} 个地雷(这个格子本身没有地雷)。 形式化地说,记

$$f(i,j)=\begin{cases} 1, & (i,j)\text{ 上有地雷} \\ 0, & \text{其他情况} \\ \end{cases} $$

特别地,对于超出棋盘边界的情况,规定 f(i,j)=0f(i,j)=0。 则 $\displaystyle S_{i,j}=\sum_{p=-1}^1\sum_{q=-1}^1 f(i+p,j+q)$。

给定一个棋盘,你可以任意决定每个 ?\texttt{?} 格子上是否有炸弹。你想要知道是否存在方案使得这个棋盘是合法的。 我们定义一个棋盘合法,当且仅当填有数字 xx 的格子周围的八个格子上恰好有 xx 个炸弹。

你需要解决 TT 组数据。

输入格式

本题单个测试点内含多组测试数据。

第一行,一个正整数 TT,代表数据组数;

对于每组数据,输入 (n+1)(n+1) 行:

  • 第一行,两个正整数 n,mn,m,描述棋盘的行数和列数;
  • 接下来 nn 行,第 (i+1)(i+1) 行的第 jj 个字符描述 Si,jS_{i,j}

输出格式

对于每组数据,输出一行。

若存在合法的方案,输出 YES;否则输出 NO

3
2 2
**
2?
2 2
*1
3?
2 2
**
21
YES
NO
NO

提示

对于第一组数据:问号处选择不填是一种合法方案。可以证明这是唯一的合法方案。

本题采用捆绑测试。

  • Subtask 1(20pts):至多存在 11(i,j)(i,j),使得 Si,j=?S_{i,j}=\texttt{?}
  • Subtask 2(80pts):无额外约束。

对于 100%100\% 的数据,保证:

  • 1T,n,m101\le T,n,m\le 10
  • 至多存在 1010(i,j)(i,j),使得 Si,j=?S_{i,j}=\texttt{?}
  • 1in,1jm\forall 1\le i\le n,1\le j\le m,保证 $S_{i,j}\in\{0,1,2,3,4,5,6,7,8,\texttt{?},\texttt{*}\}$。