Description

Minesweeper（扫雷）是一款在 20 世纪 80 年代流行起来的电脑游戏，至今仍被包含在某些版本的 Microsoft Windows 操作系统中。本题的设定与该游戏类似，但不要求你玩过扫雷。

在本题中，你将在一个由若干相同方格组成的网格上进行游戏。每个格子中的内容在初始时是隐藏的。共有 $M$ 枚地雷被隐藏在 $M$ 个不同的格子中，其他格子中不含地雷。你可以点击任意一个格子来揭示其内容。如果你点开的格子中有地雷，游戏立刻结束，你失败。否则，该格子将显示一个介于 $0$ 到 $8$ 之间的数字，表示与该格子相邻的格子中包含地雷的数量。两个格子被认为是相邻的，当且仅当它们共享一个边或一个角。

此外，如果你揭示的格子显示的是 $0$，则其所有相邻格子也会被自动揭示，并递归地继续这个过程。当所有不含地雷的格子都被揭示时，游戏结束，你获胜。

例如，一个初始的棋盘配置可能如下所示（* 表示地雷，c 表示首次点击的格子）：

*..*...**.
....*.....
..c..*....
........*.
..........

点击的格子周围没有地雷，因此被揭示后显示为 $0$，并触发其 8 个相邻格子的自动揭示。这个过程继续进行，最终得到如下棋盘：

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时，仍有一些未被揭示的、且不含地雷的格子（用 . 表示），因此玩家必须再次点击以继续游戏。

你希望尽可能快地赢得游戏。最快的方式自然是只点击一次就获胜。给定棋盘的大小（$R \times C$）以及隐藏的地雷数 $M$，请判断是否存在一种（哪怕极不可能）配置，使得玩家只需点击一次就能赢得游戏？你可以自由选择点击的位置。如果存在这样的配置，请输出任意一种符合要求的地雷布置及点击坐标，具体格式见输出说明；如果不存在，则输出 "Impossible"。

Input Format

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

Output Format

对于每个测试用例，输出一行 "Case #x:"，其中 $x$ 是当前测试用例的编号（从 $1$ 开始）。随后输出 $R$ 行，每行包含 $C$ 个字符，表示棋盘的布置。使用 . 表示空格，* 表示含有地雷的格子，c 表示被点击的格子。

如果不存在符合要求的棋盘配置，则在 "Case #x:" 之后输出一行 "Impossible"，而非棋盘内容。若存在多种可能的配置，输出其中任意一种即可。

5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82

Case #1:
Impossible
Case #2:
c
.
*
Case #3:
Impossible
Case #4:
......*
.c....*
.......
..*....
Case #5:
**********
**********
**********
****....**
***.....**
***.c...**
***....***
**********
**********
**********

Hint

限制条件

$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 完成。