P6996 [NEERC 2013] ASCII Puzzle

Fili 和 Floi 玩一个拼图游戏。Fili 拿出一张用 $W \times H$ 网格线划分的矩形纸，在网格线上将其切成若干块，并小心地将这些块打乱，但不旋转。Floi 必须在不旋转的情况下将这些块重新组合成矩形。 Fili 在将原始纸张切成块时遵循了一些约束，以确保生成的拼图是合理的。首先，Fili 选择三个整数 $w, h$ 和 $n$，使得原始矩形纸的宽度为 $W = w_n$ 个单元格，高度为 $H = h_n$ 个单元格。这里 $w$ 和 $h$ 是 Floi 已知的，但 $n, W$ 和 $H$ 是未知的。这样，原始矩形纸可以被切割成一个简单的 $k = n^{2}$ 个矩形拼图，每个矩形的宽度为 $w$ 个单元格，高度为 $h$ 个单元格。然而，对于 $k > 1$ 的简单拼图不被认为是这个游戏的合理拼图。相反，原始矩形被切割成的块是基于这些简单的 $w \times h$ 单元格矩形，并在相邻块之间有锯齿边缘。正式地说，原始 $W \times H$ 纸张被切割成的块满足以下合理拼图的约束： 有 $k = n^{2}$ 个块。 每个块是一个简单的 $4$ 连通的无孔单元格区域。 原始矩形 $W \times H$ 纸张的每个单元格恰好属于一个块。 每个块包含原始纸张简单拼图中对应 $w \times h$ 矩形的四个角。 每个块的单元格只能来自简单拼图中对应的 $w \times h$ 矩形、与该矩形相邻的单元格以及简单拼图中相邻矩形的内部单元格。 两个相邻块之间的切割不能是直的。只有位于原始 $W \times H$ 纸张边界上的块才有直边。 这些约束的推论是，每个合理拼图的块都适合一个 $(3w - 2) \times (3h - 2)$ 单元格的矩形。此外，每个块的描述将以 $(3w - 2) \times (3h - 2)$ 的单元格网格给出，使得简单拼图中对应的 $w \times h$ 矩形正好位于中心。 下图左侧显示了一张样例矩形纸，用 $W \times H = 12 \times 9$ 的方格网格划分，并用粗虚线切割成一个简单拼图，包含 $k = 9$ 个宽度为 $w = 4$ 个单元格，高度为 $h = 3$ 个单元格的矩形。这个简单拼图的中央 $3 \times 4$ 块的角用黑色显示。它们必须是任何合理拼图的中央块的一部分。合理拼图中央块的其他潜在单元格用灰色显示。粗黑线显示了 $(3w - 2) \times (3h - 2) = 10 \times 7$ 的矩形区域，将描述这个中央块。右图显示了拼图右上角块的相同情况。  你的任务是帮助 Floi 解决这个拼图。

输入文件的第一行包含三个整数 $k, w$ 和 $h$。这里 $k$ 是拼图中的块数，$w$ 是简单拼图块的宽度，$h$ 是高度（$k = n^{2}$ 且 $1 \le n \le 4, 3 \le w, h \le 5$）。输入文件的其余部分包含 $k$ 个合理拼图块的描述。每个块由 $3h - 2$ 行描述，每行包含 $3w - 2$ 个字符。块用连续的大写英文字母标记（第一个块为 'A'，第二个块为 'B'，等等）。每个块描述在其 $3h - 2$ 行中仅使用两个字符。与块对应的英文字母表示属于该块的单元格，而 '.'（点）字符表示不属于的单元格。 空行分隔不同的块。

输出文件的第一行应包含 $W$ 和 $H$——被切割成拼图块的原始纸张的大小。接下来的 $H$ 行应包含 $W$ 个英文字母，描述拼图的解决方案。字母表示属于相应拼图块的单元格。如果有多种方法可以解决拼图，则输出任意一个解决方案。

时间限制：1 秒，内存限制：128 MB。 题面翻译由 ChatGPT-4o 提供。