Линии

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

В таблице из n строк и n столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

Входные данные

В первой строке находится число n (2 ≤ n ≤ 40), в каждой из следующих n строк - по n символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика.

Выходные данные

В первой строке вывести Y, если движение возможно, или N, если нет. Если движение возможно, то далее следуют n строк по n символов - как и на вводе, но X, а также все точки на пути заменяются плюсами.

Пример

Входные данные #1

5
....X
.OOOO
.....
OOOO.
@....

Выходные данные #1

Y
+++++
+OOOO
+++++
OOOO+
@++++

Входные данные #2

5
..X..
.....
OOOOO
.....
..@..

Выходные данные #2

Входные данные #3

5
...X.
.....
O.OOO
.....
....@

Выходные данные #3

Y
..++.
.++..
O+OOO
.++++
....@

Показать классификацию задачи