e-olymp
Задачи

Линии

Линии

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
5
....X
.OOOO
.....
OOOO.
@....
Выходные данные #1
Y
+++++
+OOOO
+++++
OOOO+
@++++
Входные данные #2
5
..X..
.....
OOOOO
.....
..@..
Выходные данные #2
N
Входные данные #3
5
...X.
.....
O.OOO
.....
....@
Выходные данные #3
Y
..++.
.++..
O+OOO
.++++
....@