← 返回题目列表

Codeforces · 538/D

D. 奇怪的国际象棋

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

伊戈尔已经玩了很长时间的国际象棋,现在他厌倦了普通规则的游戏。他将想出新的游戏规则并变得举世闻名。

Igor 的棋盘是一个大小为 n × n 个单元的正方形。伊戈尔认为简单的规则就能保证成功,这就是为什么他的游戏只有一种类型的棋子。此外,他的游戏中的所有棋子都是相同的颜色。棋子可能的移动由一组移位向量描述。下一段包含可用动作的正式描述。

让棋盘的行从上到下编号,列从左到右从 1 到 n 编号。让我们为每个方格分配一对整数 (x, y)——相应列和行的编号。该棋子的每个可能的移动都由一对整数(dx,dy)定义;使用此移动,棋子从区域 (x, y) 移动到区域 (x + dx, y + dy)。如果单元格 (x + dx, y + dy) 位于棋盘边界内并且不包含其他棋子,则可以执行移动。在考虑进行给定移动的可能性时(例如,当马在通常的国际象棋中移动时),除 (x, y) 和 (x + dx, y + dy) 之外的单元格上的棋子并不重要。

伊戈尔让你看看他的棋子可以走什么棋。他在棋盘上放置了几个棋子,对于每个未占据的方格,他告诉您它是否受到任何现有棋子的攻击(即,场上的某些棋子是否可以移动到该单元格)。恢复该棋子的一组可能的移位向量,否则确定Igor犯了错误并且对于任何一组移位向量都不可能出现这种情况。

输入

第一行包含一个整数 n (1 ≤ n ≤ 50)。

接下来的 n 行包含 n 个字符,每个字符描述 Igor 提供的位置。第 i 个字符串的第 j 个字符可以具有以下值:

- o — 在这种情况下,场地 (i, j) 被一个棋子占据,并且该场地可能会也可能不会被其他棋子攻击;
- x — 在这种情况下,场 (i, j) 受到某些棋子的攻击;
- . — 在这种情况下,场 (i, j) 没有受到任何棋子的攻击。

保证棋盘上至少有一颗棋子。

输出

如果存在一组有效的移动,则在第一行中打印一个单词“YES”(不带引号)。接下来,以 (2n - 1) × (2n - 1) 棋盘的形式打印棋子的走法集合的描述,棋盘的中心有一个棋子,符号“x”标记受棋子攻击的单元格,格式与输入类似。请参阅输出示例以充分了解该格式。如果有多个可能的答案,请打印其中任何一个。

如果不存在有效的移动集,则打印一个单词“NO”。

示例

输入 #1

5
oxxxx
x...x
x...x
x...x
xxxxo

输出 #1

YES
....x....
....x....
....x....
....x....
xxxxoxxxx
....x....
....x....
....x....
....x....

输入 #2

6
.x.x..
x.x.x.
.xo..x
x..ox.
.x.x.x
..x.x.

输出 #2

YES
...........
...........
...........
....x.x....
...x...x...
.....o.....
...x...x...
....x.x....
...........
...........
...........

输入 #3

3
o.x
oxx
o.x

输出 #3

NO

注意

在第一个样本测试中,棋子是通常的国际象棋车,在第二个样本测试中,棋子是通常的国际象棋马。