编程题
### 问题描述 扫雷是一款经典的游戏。如下图: ![图片描述](https://dn-simplecloud.shiyanlou.com/questions/uid1792586-20231214-1702530411073) 规则如下。 1. 地图为 $n \times m$ 的矩阵。 2. 地图中包含地雷和数字。 3. 如果某个点是地雷块,那么用 `X` 表示。 4. 如果某个点是数字块,那么用 $0 \sim 8$ 表示,具体的数值为该点周围地雷的数量(最少为 $0$ 个,最多为 $8$ 个)。 5. 如果某个点未知,即可能是地雷或者数字,我们用 `*` 表示。 **周围**:对于 $(x,y)$ 点来说,周围为 $(x-1, y),(x+1, y),(x, y-1),(x, y+1),(x-1, y-1),(x-1, y+1),(x+1, y-1),(x+1, y+1)$ 八个位置。需要注意的是,**超过边界的点不能算作周围的点**。 了解上述规则后,我们得知,可以通过数字块推理出地雷的位置。 小蓝是扫雷高手,他点开了一局游戏。 玩了一段时间之后,他发现没法推断出来到底哪些块是地雷(如上述图片),他感到十分厌烦,觉得这个游戏有 BUG。 于是小蓝找到了你,想让你用计算机判断一下,某些地图残局是否有 BUG。 具体来说,小蓝给你一幅 $n \times m$ 的地图,地图中只包含数字和 `*`(不包含 `X`,因为不能点开雷区),小蓝想知道,对于该局面,能否**直接**推断出所有的 `*` 的值。如果可以,代表该局面的解唯一,即没有 BUG;如果不能,小蓝就是会认为该局面的解不唯一,游戏产生了 BUG。 ### 输入格式 第一行一个整数 $T$,代表扫雷地图数量。 对于每一个地图,由以下部分构成: 1. 第一行输入两个整数 $n,m$。 2. 接下面 $n$ 行,每行输入 $m$ 个字符。 ### 输出格式 输出 $T$ 行。 第 $i$ 行对应第 $i$ 个地图的解情况,每行输出一个字符串:输出 `Single` 代表只有一种解,即无 BUG,输出 `Multiple` 代表存在多个解,即有 BUG。 ### 样例输入 ```bash 2 3 5 01*10 011*0 00000 3 3 *** 232 *** ``` ### 样例输出 ```bash Single Multiple ``` ### 说明 第一个样例就只有一种解: ```bash 01X10 01110 00000 ``` 第二组样例存在如下多组解: ```bash XX1 01X XXX 232 232 232 01X XX1 000 ``` ### 评测数据范围 $1 \le n \times m \le 100,1 \le T \le 100$。 保证输入中**只包含**:`*` 和数字字符,并且至少存在一种合法地图解,即不会存在自相矛盾的残局。 每组的 `*` 不会超过 $16$ 个。
查看答案
赣ICP备20007335号-2