Codeforces Round 300 |
---|
Закончено |
Игорь много занимался шахматами, и теперь ему надоела игра по обычным правилам. Он собирается придумать новые правила игры и обрести мировую славу.
Доска в шахматах Игоря имеет форму квадрата n × n клеток. Игорь решил, что простота правил — залог успеха, поэтому в его игре будет всего один тип фигур, кроме того, все фигуры в его игре одного цвета. Всевозможные ходы фигуры описываются множеством векторов смещений. В следующем абзаце находится формальное описание допустимых ходов.
Пусть горизонтали доски пронумерованы сверху вниз, а вертикали — слева направо от 1 до n. Сопоставим каждой клетке пару чисел (x, y) — номер соответствующей вертикали и горизонтали. Каждый из возможных ходов фигуры задается парой чисел (dx, dy), используя этот ход, фигура с поля (x, y) перемещается на поле (x + dx, y + dy). Ход можно совершить, если поле (x + dx, y + dy) находится внутри границ доски, и на нем нет другой фигуры. Фигуры, стоящие на полях, отличных от (x, y) и (x + dx, y + dy), не влияют на возможность совершения данного хода (например, как при ходе коня в обычных шахматах).
Игорь предлагает вам угадать, какие ходы может делать его фигура. Он расставил на доске несколько фигур и про каждое незанятое поле сообщил вам, находится ли оно под боем хотя бы одной фигуры (т.е. может ли какая-либо из стоящих на поле фигур сходить в это поле). Восстановите возможный набор ходов фигуры, либо определите, что Игорь ошибся и такая ситуация невозможна ни при каком наборе ходов.
В первой строке записано одно целое число n (1 ≤ n ≤ 50).
В следующих n строках записано по n символов, которые описывают предложенную Игорем позицию. j-й символ i-й строки может принимать значения:
Гарантируется, что на доске присутствует хотя бы одна фигура.
Если допустимое множество ходов существует, в первой строке выведите одно слово «YES» (без кавычек). Далее, выведите описание множества ходов фигуры в виде доски (2n - 1) × (2n - 1), в центре которой находится фигура, а символами 'x' отмечены атакуемые ею клетки, в формате, аналогичном формату ввода. Смотрите примеры вывода для полного понимания формата. Если существует несколько возможных вариантов ответа, выведите любой из них.
Если допустимого множества ходов не существует, выведите единственное слово «NO».
5
oxxxx
x...x
x...x
x...x
xxxxo
YES
....x....
....x....
....x....
....x....
xxxxoxxxx
....x....
....x....
....x....
....x....
6
.x.x..
x.x.x.
.xo..x
x..ox.
.x.x.x
..x.x.
YES
...........
...........
...........
....x.x....
...x...x...
.....o.....
...x...x...
....x.x....
...........
...........
...........
3
o.x
oxx
o.x
NO
В первом тесте из условия изображена обычная шахматная ладья, во втором тесте из условия — обычный шахматный конь.
Название |
---|