P13371 [GCJ 2011 #1C] Square Tiles

你正在出售美丽的几何画作。每幅画由 $1\times 1$ 的方块瓷砖组成，排列成不重叠的网格。例如： ``` .##.. .#### .#### .##.. ``` 蓝色瓷砖用字符 '#' 表示，白色瓷砖用字符 '.' 表示。你不会使用其他颜色。 但并不是每个人都喜欢蓝色，有些顾客希望你把画中的所有蓝色瓷砖都换成红色瓷砖。不幸的是，红色瓷砖只能是更大的 $2\times 2$ 尺寸，这让事情变得棘手。 你可以用一块红色瓷砖覆盖任意一个 $2\times 2$ 的蓝色瓷砖区域，然后重复此操作直到完成。红色瓷砖不能重叠，不能覆盖白色瓷砖，也不能超出画作边界。例如，你可以如下方式在上面的画作中添加红色瓷砖： ``` ./\.. .\//\ ./\\/ .\/.. ``` 每块红色瓷砖用左上和右下角的 '/' 字符，以及另外两个角的 '\\' 字符表示。 给定一幅蓝白画作，你能否用这种方式将其转换为红白画作？

输入的第一行给出测试用例数 $T$。接下来有 $T$ 组测试用例。 每组测试用例的第一行包含两个整数 $R$ 和 $C$，表示画作的行数和列数。接下来的 $R$ 行，每行包含恰好 $C$ 个字符，描述画作。'#' 表示蓝色瓷砖，'.' 表示白色瓷砖。

对于每组测试用例，首先输出一行 "Case #$x$: "，其中 $x$ 是测试用例编号（从 1 开始）。 如果可以用不重叠的红色瓷砖覆盖所有蓝色瓷砖，输出 $R$ 行，每行 $C$ 个字符，描述最终的红白画作。红色瓷砖用 '/' 和 '\\' 字符表示，白色瓷砖用 '.' 表示。如果有多种方案，可以输出任意一种。 如果无法完成任务，输出一行 "Impossible"。

**数据范围** **小数据集（10 分，测试集 1 - 可见）** - $1 \leq T \leq 20$。 - $1 \leq R \leq 6$。 - $1 \leq C \leq 6$。 - 时间限制：~~30~~ 3 秒。 **大数据集（10 分，测试集 2 - 隐藏）** - $1 \leq T \leq 50$。 - $1 \leq R \leq 50$。 - $1 \leq C \leq 50$。 - 时间限制：~~60~~ 6 秒。 由 ChatGPT 4.1 翻译