CF1284G Seollal

距离韩国农历新年（Seollal）只有几天了，Jaehyun 邀请了家人来到他的花园。来宾中有一些孩子。为了让聚会更有趣，Jaehyun 打算为孩子们举办一场捉迷藏游戏。 花园可以用一个 $n \times m$ 的单元格网格表示。其中一些（可能为零）单元格被石头阻挡，其余单元格是空地。如果两个单元格有公共边，则它们是相邻的。每个单元格最多有 4 个相邻单元格：水平方向两个，垂直方向两个。 由于花园用网格表示，我们可以将花园中的单元格分为“黑色”和“白色”两类。左上角的单元格是黑色的，相邻的两个单元格颜色必须不同。单元格下标从 1 开始，因此花园左上角的单元格为 $(1, 1)$。 Jaehyun 想通过在两个单元格之间放置一些墙壁，将花园变成一个迷宫。墙壁只能放在相邻的两个单元格之间。如果在相邻的两个单元格 $a$ 和 $b$ 之间放了一堵墙，那么从此 $a$ 和 $b$ 就不再是相邻单元格。只有当两个相邻单元格之间没有墙时，才能直接从一个单元格走到另一个单元格。 迷宫必须满足以下性质：对于迷宫中的每一对空地单元格，二者之间恰好存在一条简单路径。两个单元格 $a$ 和 $b$ 之间的简单路径是指一系列空地单元格，起点为 $a$，终点为 $b$，所有单元格互不相同，且任意相邻的两个单元格是相邻且之间没有墙阻挡的。 一开始，孩子们会聚集在 $(1, 1)$ 单元格，开始捉迷藏游戏。一个孩子可以藏在一个单元格中，当且仅当该单元格是空地，不是 $(1, 1)$，并且恰好有一个空地相邻单元格。Jaehyun 在黑色单元格中种了玫瑰，所以孩子们藏在那里很危险。因此，Jaehyun 希望创建一个迷宫，使得孩子们只能藏在白色单元格中。 你将获得花园的地图作为输入。你的任务是帮助 Jaehyun 创建一个迷宫。

你的程序将被多个测试用例评测。 第一行包含测试用例数 $t$。（$1 \le t \le 100$）。接下来是 $t$ 个测试用例，每个用例格式如下： 每个测试用例的第一行包含两个整数 $n, m$（$2 \le n, m \le 20$），表示网格的大小。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，仅由以下字符组成（无空格）： - O：空地单元格。 - X：石头单元格。 保证第一个单元格（$(1, 1)$）是空地，且每个空地单元格都可以从 $(1, 1)$ 到达。 如果 $t \geq 2$，则网格大小满足 $n \le 10, m \le 10$。换句话说，如果输入中有 $n > 10$ 或 $m > 10$ 的网格，则该测试用例是唯一的（$t = 1$）。

对于每个测试用例，输出如下： 如果不存在可能的迷宫，输出一行 NO。 否则，输出一行 YES，接着输出一个大小为 $(2n-1) \times (2m-1)$ 的网格，表示找到的迷宫。迷宫的输出规则如下，所有单元格下标从 1 开始： - 对于所有 $1 \le i \le n, 1 \le j \le m$，如果 $(i, j)$ 是空地单元格，则在 $(2i-1, 2j-1)$ 处输出 'O'；否则输出 'X'。 - 对于所有 $1 \le i \le n, 1 \le j \le m-1$，如果相邻单元格 $(i, j)$ 和 $(i, j+1)$ 之间有墙，则在 $(2i-1, 2j)$ 处输出空格 ' '；否则输出任意可打印字符（但不能是空格）。可打印字符的 ASCII 码范围为 $[32, 126]$，包括空格和字母数字。 - 对于所有 $1 \le i \le n-1, 1 \le j \le m$，如果相邻单元格 $(i, j)$ 和 $(i+1, j)$ 之间有墙，则在 $(2i, 2j-1)$ 处输出空格 ' '；否则输出任意可打印字符（但不能是空格）。 - 对于所有 $1 \le i \le n-1, 1 \le j \le m-1$，在 $(2i, 2j)$ 处输出任意可打印字符。 请注意行末不要有多余的换行或空格。每一行应恰好包含 $2m-1$ 个字符，行与行之间用换行符分隔。行末不能省略空格。

由 ChatGPT 4.1 翻译