← 返回题目列表

Codeforces · 1284/G

G. 春节

中文机器翻译题面 查看原题

距离农历新年只有几天了,Jaehyun 邀请家人去他的花园。客人中有孩子。为了让孩子们的聚会变得更有趣,在玹将举办一场捉迷藏游戏。

花园可以用 $$$n \times m$$$ 单位单元格表示。一些(可能是零)单元格被岩石阻挡,其余单元格是自由的。如果两个单元共享一条边,则它们是邻居。每个单元最多有 4 个邻居:两个​​在水平方向,两个在垂直方向。

由于花园表示为网格,因此我们可以将花园中的单元格分类为“黑色”或“白色”。左上角的单元格是黑色的,相邻的两个单元格必须是不同的颜色。单元格索引从 1 开始,因此花园的左上角是单元格 $$$(1, 1)$$$。

Jaehyun 想要通过在两个牢房之间放置一些墙壁来将他的花园变成迷宫。墙壁只能放置在相邻单元格之间。如果墙放置在两个相邻单元格 $$$a$$$ 和 $$$b$$$ 之间,则从该点开始这两个单元格 $$$a$$$ 和 $$$b$$$ 不相邻。当且仅当两个相邻的牢房之间没有直接的墙壁时,人们才能直接在两个相邻的牢房之间行走。

迷宫必须具有以下属性。对于迷宫中的每一对自由单元,它们之间必须存在一条简单路径。单元格 $$$a$$$ 和 $$$b$$$ 之间的简单路径是一系列空闲单元格,其中第一个单元格是 $$$a$$$,最后一个单元格是 $$$b$$$,所有单元格都是不同的,并且任何两个连续的单元格是没有直接被墙壁阻挡的邻居。

首先,孩子们会聚集在牢房$$$(1, 1)$$$中,开始捉迷藏游戏。当且仅当该单元格是空闲的,它不是 $$$(1, 1)$$$,并且恰好有一个空闲的邻居时,孩子才能隐藏在该单元格中。在玹在黑色牢房里种了玫瑰,所以如果孩子们躲在那里就会很危险。所以在玹想要创造一个迷宫,孩子们只能躲在白细胞里。

您将获得花园地图作为输入。你的任务是帮助在玹创造一个迷宫。

输入

您的程序将在多个测试用例中进行评判。

第一行包含测试用例的数量$$$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'。否则,在单元格 $$$(2i-1, 2j-1)$$$ 中打印“X”。
- 对于所有 $$$1 \le i \le n, 1 \le j \le m-1$$$,如果相邻单元格 $$$(i, j), (i, j+1)$$$ 有墙挡住,则在单元格 $$$(2i-1, 2j)$$$ 中打印 ' '。否则,打印单元格 $$$(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)$$$ 中打印 ' '。否则,打印单元格中除空格之外的任何可打印字符 $$$(2i, 2j-1)$$$
- 对于所有 $$$1 \le i \le n-1, 1 \le j \le m-1$$$,打印单元格 $$$(2i, 2j)$$$ 中的任何可打印字符。

请小心尾随换行符或空格。网格的每一行应恰好包含 $$$2m-1$$$ 字符,并且行应以换行符分隔。一行中不得省略尾随空格。

示例

输入 #1

4
2 2
OO
OO
3 3
OOO
XOO
OOO
4 4
OOOX
XOOX
OOXO
OOOO
5 6
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO

输出 #1

YES
OOO
  O
OOO
NO
YES
OOOOO X
  O O  
X O O X
  O    
OOO X O
O O   O
O OOOOO
YES
OOOOOOOOOOO
  O   O   O
OOO OOO OOO
O   O   O  
OOO OOO OOO
  O   O   O
OOO OOO OOO
O   O   O  
OOO OOO OOO