P13245 [GCJ 2014 Qualification] Minesweeper Master

**Minesweeper**（扫雷）是一款在 20 世纪 80 年代流行起来的电脑游戏，至今仍被包含在某些版本的 Microsoft Windows 操作系统中。本题的设定与该游戏类似，但不要求你玩过扫雷。 在本题中，你将在一个由若干相同方格组成的网格上进行游戏。每个格子中的内容在初始时是隐藏的。共有 $M$ 枚地雷被隐藏在 $M$ 个不同的格子中，其他格子中不含地雷。你可以点击任意一个格子来揭示其内容。如果你点开的格子中有地雷，游戏立刻结束，你失败。否则，该格子将显示一个介于 $0$ 到 $8$ 之间的数字，表示与该格子相邻的格子中包含地雷的数量。两个格子被认为是相邻的，当且仅当它们共享一个边或一个角。 此外，如果你揭示的格子显示的是 $0$，则其所有相邻格子也会被自动揭示，并递归地继续这个过程。当所有不含地雷的格子都被揭示时，游戏结束，你获胜。 例如，一个初始的棋盘配置可能如下所示（`*` 表示地雷，`c` 表示首次点击的格子）： ``` *..*...**. ....*..... ..c..*.... ........*. .......... ``` 点击的格子周围没有地雷，因此被揭示后显示为 $0$，并触发其 8 个相邻格子的自动揭示。这个过程继续进行，最终得到如下棋盘： ``` *..*...**. 1112*..... 00012*.... 00001111*. 00000001.. ``` 此时，仍有一些未被揭示的、且不含地雷的格子（用 `.` 表示），因此玩家必须再次点击以继续游戏。 你希望尽可能快地赢得游戏。最快的方式自然是**只点击一次就获胜**。给定棋盘的大小（$R \times C$）以及隐藏的地雷数 $M$，请判断是否存在一种（哪怕极不可能）配置，使得玩家只需点击一次就能赢得游戏？你可以自由选择点击的位置。如果存在这样的配置，请输出任意一种符合要求的地雷布置及点击坐标，具体格式见输出说明；如果不存在，则输出 **"Impossible"**。

输入的第一行是测试用例的数量 $T$。接下来的 $T$ 行，每行包含三个用空格分隔的整数：$R$、$C$ 和 $M$。

对于每个测试用例，输出一行 `"Case #x:"`，其中 $x$ 是当前测试用例的编号（从 $1$ 开始）。随后输出 $R$ 行，每行包含 $C$ 个字符，表示棋盘的布置。使用 `.` 表示空格，`*` 表示含有地雷的格子，`c` 表示被点击的格子。 如果不存在符合要求的棋盘配置，则在 `"Case #x:"` 之后输出一行 **"Impossible"**，而非棋盘内容。若存在多种可能的配置，输出其中任意一种即可。

**限制条件** $0 \leq M < R \times C$。 **小数据集（11 分）** - 时间限制：~~60~~ 3 秒。 - $1 \leq T \leq 230$。 - $1 \leq R, C \leq 5$。 **大数据集（24 分）** - 时间限制：~~120~~ 5 秒。 - $1 \leq T \leq 140$。 - $1 \leq R, C \leq 50$。 翻译由 ChatGPT-4o 完成。