{"problem":{"name":"[GXPC-S 2024] 扫雷","description":{"content":"一个扫雷游戏可以被抽象成一个 $n$ 行 $m$ 列的字符矩阵，不妨记第 $i$ 行第 $j$ 列的字符为 $S_{i,j}$。 若 $S_{i,j}=\\texttt{*}$，表示格子 $(i,j)$ 上有一个地雷； 若 $S_{i,j}=\\texttt{?}$，表示格子 $(i,j)$ 情况未知； 若 $S_{i,j}\\in [0,8]$，表示格子 $(i,j)$ 周围的 $8$ 个格子中","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4167"},"statements":[{"statement_type":"Markdown","content":"一个扫雷游戏可以被抽象成一个 $n$ 行 $m$ 列的字符矩阵，不妨记第 $i$ 行第 $j$ 列的字符为 $S_{i,j}$。\n\n若 $S_{i,j}=\\texttt{*}$，表示格子 $(i,j)$ 上有一个地雷；\n\n若 $S_{i,j}=\\texttt{?}$，表示格子 $(i,j)$ 情况未知；\n\n若 $S_{i,j}\\in [0,8]$，表示格子 $(i,j)$ 周围的 $8$ 个格子中有 $S_{i,j}$ 个地雷（这个格子本身没有地雷）。\n形式化地说，记\n\n$$\nf(i,j)=\\begin{cases}\n1, & (i,j)\\text{ 上有地雷} \\\\\n0, & \\text{其他情况} \\\\\n\\end{cases}\n$$\n\n特别地，对于超出棋盘边界的情况，规定 $f(i,j)=0$。\n则 $\\displaystyle S_{i,j}=\\sum_{p=-1}^1\\sum_{q=-1}^1 f(i+p,j+q)$。\n\n给定一个棋盘，你可以任意决定每个 $\\texttt{?}$ 格子上是否有炸弹。你想要知道是否存在方案使得这个棋盘是合法的。\n我们定义一个棋盘**合法**，当且仅当填有数字 $x$ 的格子周围的八个格子上恰好有 $x$ 个炸弹。\n\n你需要解决 $T$ 组数据。\n\n## Input\n\n**本题单个测试点内含多组测试数据。**\n\n第一行，一个正整数 $T$，代表数据组数；\n\n对于每组数据，输入 $(n+1)$ 行：\n\n- 第一行，两个正整数 $n,m$，描述棋盘的行数和列数；\n- 接下来 $n$ 行，第 $(i+1)$ 行的第 $j$ 个字符描述 $S_{i,j}$。\n\n## Output\n\n对于每组数据，输出一行。\n\n若存在合法的方案，输出 `YES`；否则输出 `NO`。\n\n[samples]\n\n## Background\n\n小林最近迷上了扫雷游戏。\n\n## Note\n\n对于第一组数据：问号处选择不填是一种合法方案。可以证明这是唯一的合法方案。\n\n**本题采用捆绑测试。**\n\n- Subtask 1（20pts）：至多存在 $1$ 组 $(i,j)$，使得 $S_{i,j}=\\texttt{?}$；\n- Subtask 2（80pts）：无额外约束。\n\n对于 $100\\%$ 的数据，保证：\n\n- $1\\le T,n,m\\le 10$；\n- 至多存在 $10$ 组 $(i,j)$，使得 $S_{i,j}=\\texttt{?}$；\n- $\\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{*}\\}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4167","tags":["模拟","搜索","2024","枚举","广西"],"sample_group":[["3\n2 2\n**\n2?\n2 2\n*1\n3?\n2 2\n**\n21","YES\nNO\nNO"]],"created_at":"2026-03-03 11:09:25"}}