Seollal

题意翻译

新年要来啦，Jaehyun 邀请了他的全家到他的花园，客人里面有小朋友，所以为了使聚会对于孩子们更好玩，Jaehyun 将要设计捉迷藏的游戏。 花园可以表示成一个 $n \times m$ 的网格图，一些格子里面有石头，剩下的格子是空着的。我们定义一个格子的邻居为其上下左右的格子，所以一个格子至多有 $4$ 个邻居。 我们把每个格子都黑白染色，染色方案为：左上角的格子 $(1,1)$ 是黑色的，每一个格子的颜色必须和他的邻居的颜色不同。 Jaehyun 要把他的花园变成一个迷宫，具体的操作方式是在两个相邻的格子之间放一堵墙。如果两个格子之见有一堵墙，则这两个格子将不再是邻居。（即：一个格子可以移动到他的邻居，前提是这两个格子之间不能有墙） 迷宫必须满足以下性质：对于任意两个空闲的格子，存在且仅存在一条简单路径（简单路径即：从一个格子出发，到达另一个格子，经过的格子不重复，且不能撞墙） 一开始的时候，孩子们会都待在 $(1,1)$，然后到一些格子里面躲藏。这些格子必须满足他们是空闲的，并且他们只有一个空闲的邻居。由于黑色的格子里面种了玫瑰花，所以 Jaehyun 要设计一个孩子们只能在白色格子里面躲藏的迷宫。 输入这个花园的地图，输出符合要求的迷宫。

题目描述

It is only a few days until Seollal (Korean Lunar New Year), and Jaehyun has invited his family to his garden. There are kids among the guests. To make the gathering more fun for the kids, Jaehyun is going to run a game of hide-and-seek. The garden can be represented by a $ n \times m $ grid of unit cells. Some (possibly zero) cells are blocked by rocks, and the remaining cells are free. Two cells are neighbors if they share an edge. Each cell has up to 4 neighbors: two in the horizontal direction and two in the vertical direction. Since the garden is represented as a grid, we can classify the cells in the garden as either "black" or "white". The top-left cell is black, and two cells which are neighbors must be different colors. Cell indices are 1-based, so the top-left corner of the garden is cell $ (1, 1) $ . Jaehyun wants to turn his garden into a maze by placing some walls between two cells. Walls can only be placed between neighboring cells. If the wall is placed between two neighboring cells $ a $ and $ b $ , then the two cells $ a $ and $ b $ are not neighboring from that point. One can walk directly between two neighboring cells if and only if there is no wall directly between them. A maze must have the following property. For each pair of free cells in the maze, there must be exactly one simple path between them. A simple path between cells $ a $ and $ b $ is a sequence of free cells in which the first cell is $ a $ , the last cell is $ b $ , all cells are distinct, and any two consecutive cells are neighbors which are not directly blocked by a wall. At first, kids will gather in cell $ (1, 1) $ , and start the hide-and-seek game. A kid can hide in a cell if and only if that cell is free, it is not $ (1, 1) $ , and has exactly one free neighbor. Jaehyun planted roses in the black cells, so it's dangerous if the kids hide there. So Jaehyun wants to create a maze where the kids can only hide in white cells. You are given the map of the garden as input. Your task is to help Jaehyun create a maze.

输入输出格式

输入格式

Your program will be judged in multiple test cases. The first line contains the number of test cases $ t $ . ( $ 1 \le t \le 100 $ ). Afterward, $ t $ test cases with the described format will be given. The first line of a test contains two integers $ n, m $ ( $ 2 \le n, m \le 20 $ ), the size of the grid. In the next $ n $ line of a test contains a string of length $ m $ , consisting of the following characters (without any whitespace): - O: A free cell. - X: A rock. It is guaranteed that the first cell (cell $ (1, 1) $ ) is free, and every free cell is reachable from $ (1, 1) $ . If $ t \geq 2 $ is satisfied, then the size of the grid will satisfy $ n \le 10, m \le 10 $ . In other words, if any grid with size $ n > 10 $ or $ m > 10 $ is given as an input, then it will be the only input on the test case ( $ t = 1 $ ).

输出格式

For each test case, print the following: If there are no possible mazes, print a single line NO. Otherwise, print a single line YES, followed by a grid of size $ (2n-1) \times (2m-1) $ denoting the found maze. The rules for displaying the maze follows. All cells are indexed in 1-base. - For all $ 1 \le i \le n, 1 \le j \le m $ , if the cell $ (i, j) $ is free cell, print 'O' in the cell $ (2i-1, 2j-1) $ . Otherwise, print 'X' in the cell $ (2i-1, 2j-1) $ . - For all $ 1 \le i \le n, 1 \le j \le m-1 $ , if the neighboring cell $ (i, j), (i, j+1) $ have wall blocking it, print ' ' in the cell $ (2i-1, 2j) $ . Otherwise, print any printable character except spaces in the cell $ (2i-1, 2j) $ . A printable character has an ASCII code in range $ [32, 126] $ : This includes spaces and alphanumeric characters. - For all $ 1 \le i \le n-1, 1 \le j \le m $ , if the neighboring cell $ (i, j), (i+1, j) $ have wall blocking it, print ' ' in the cell $ (2i, 2j-1) $ . Otherwise, print any printable character except spaces in the cell $ (2i, 2j-1) $ - For all $ 1 \le i \le n-1, 1 \le j \le m-1 $ , print any printable character in the cell $ (2i, 2j) $ . Please, be careful about trailing newline characters or spaces. Each row of the grid should contain exactly $ 2m-1 $ characters, and rows should be separated by a newline character. Trailing spaces must not be omitted in a row.

输入输出样例

输入样例 #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

题意翻译

新年要来啦，Jaehyun 邀请了他的全家到他的花园，客人里面有小朋友，所以为了使聚会对于孩子们更好玩，Jaehyun 将要设计捉迷藏的游戏。 花园可以表示成一个 $n \times m$ 的网格图，一些格子里面有石头，剩下的格子是空着的。我们定义一个格子的邻居为其上下左右的格子，所以一个格子至多有 $4$ 个邻居。 我们把每个格子都黑白染色，染色方案为：左上角的格子 $(1,1)$ 是黑色的，每一个格子的颜色必须和他的邻居的颜色不同。 Jaehyun 要把他的花园变成一个迷宫，具体的操作方式是在两个相邻的格子之间放一堵墙。如果两个格子之见有一堵墙，则这两个格子将不再是邻居。（即：一个格子可以移动到他的邻居，前提是这两个格子之间不能有墙） 迷宫必须满足以下性质：对于任意两个空闲的格子，存在且仅存在一条简单路径（简单路径即：从一个格子出发，到达另一个格子，经过的格子不重复，且不能撞墙） 一开始的时候，孩子们会都待在 $(1,1)$，然后到一些格子里面躲藏。这些格子必须满足他们是空闲的，并且他们只有一个空闲的邻居。由于黑色的格子里面种了玫瑰花，所以 Jaehyun 要设计一个孩子们只能在白色格子里面躲藏的迷宫。 输入这个花园的地图，输出符合要求的迷宫。