P13154 [GCJ 2018 Finals] Two-Tiling

你的游戏公司刚刚订购了许多有 $64$ 个空白单元格的正方形游戏棋盘，原本打算将它们制作为国际象棋棋盘，但你的老板突然宣布国际象棋已经过时。为了充分利用这些棋盘，你设计了一种新的拼图游戏，使用“瓷砖”。 一个“瓷砖”是由若干个单元格通过边相连组成的连续区域，且可以放入一个 $3\times 3$ 的单元格正方形内。例如，以下是一些合法的瓷砖示例（每个 @ 表示瓷砖的一部分，额外的 . 字符用于填充）： ``` ... @@@ @@@ .@@ ... @@@ @.@ @.@ .@. @@@ @.. @@@ ``` 以下则不是合法的瓷砖： ``` @@. @.@ .@@. ... .@. @@@@ .@@ @.@ .@@. ``` 当玩家在棋盘上放置瓷砖时，瓷砖的单元格必须完全覆盖棋盘上未被其他瓷砖覆盖的某些单元格。即使经过任意平移、90 度倍数的旋转和/或翻转后，仍然视为同一种瓷砖，玩家在放置时可以进行这些操作。例如，以下所有都是同一种瓷砖（还可能有其它变体）： ``` .@. ..@ @.. ... @@. @@. .@@ @@. .@@ .@@ @.. .@. .@. @@. ... ``` 为了制作拼图，你会将棋盘上的一个或多个单元格涂成红色。玩家需要通过放置瓷砖，使所有红色单元格都被覆盖，且没有其他单元格被覆盖。为节省制造成本，玩家只会获得一种瓷砖，但会获得恰好足够多的该瓷砖以覆盖所有红色单元格。 你的任务是决定哪些棋盘单元格需要涂成红色。不幸的是，你的老板还在犹豫究竟用哪两种瓷砖。你厌倦了等待，于是决定尝试涂色，使得无论最终选择哪种瓷砖，拼图都能被解出。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试用例；每组包含四行。前三行每行有三个字符，然后一个空格，再三个字符。第四行为空行。 每组测试用例中，空格将左侧和右侧的两个 $3\times 3$ 网格分开。每个网格表示一种瓷砖的形状。网格中的每个字符要么是 @（表示瓷砖的一部分），要么是 .（表示不是瓷砖的一部分，仅用于填充以便形状清晰）。注意，这些 . 与拼图或棋盘无关，仅用于展示瓷砖形状。保证输入的两种瓷砖不是同一种瓷砖（如上文所述）。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 POSSIBLE（存在解）或 IMPOSSIBLE（不存在解）。如果存在解，则再输出八行，每行十七个字符，形成两个 $8\times 8$ 的网格，中间用一个空格分隔。每个网格用点（.）表示空白单元格，或用如下 64 个字符之一： ``` !?0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ``` 表示每个瓷砖的不同部分。在每个 $8\times 8$ 网格中，相同的非点字符表示同一个瓷砖的不同部分，不同字符表示不同的瓷砖。左侧网格中的每个瓷砖必须与输入左侧的瓷砖一致（允许旋转、平移和翻转），右侧网格同理。两个 $8\times 8$ 网格中非点字符所在的单元格集合必须完全相同，且非空。 如果有多组合法解，可以输出任意一组。

**样例解释** 样例输出展示了样例的某一组答案，其他答案也可能合法。 在样例第 2 组中，不存在一组红色单元格能使得无论选择哪种瓷砖都能解出拼图。 在样例第 3、4 组中，所选的红色单元格不要求连通。注意，输入中瓷砖的点（.）不参与拼图，仅用于展示。例如，以下输入也可以接受： ``` ... ... .@. .@. ... .@. ``` 此外，该输入与样例第 4 组同构，因此不会同时出现在同一测试集中。 **第 1 组数据范围（可见，且为唯一测试集）** - $T = 595$。（包含所有可能的测试用例，按同构分类） - 输入中每个瓷砖的单元格通过边相连，形成一个连通块。 - 输入的两种瓷砖不是同一种瓷砖（如上文所述）。 由 ChatGPT 4.1 翻译