В таблице из N строк и N столбцов некоторые клетки заняты
шариками, другие свободны. Выбран шарик, который нужно переместить, и место,
куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю
по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли
переместить шарик из начальной клетки в заданную, и если возможно, то найти
путь из наименьшего количества шагов.
Ограничения: 2 <= N <= 250,
время 1 с.
Ввод. В первой строке находится число N,
в следующих N строках - по N символов. Символом '.' обозначена
свободная клетка, латинской заглавной 'O' - шарик, '@' -
исходное положение шарика, который должен двигаться, латинской заглавной
'X' - конечное положение шарика.
Вывод. В первой строке выводится 'Y', если
движение возможно, или 'N', если нет. Если движение возможно, далее
следует N строк по N символов - как и на вводе, но
'X', а также все точки по пути заменяются символом '+'.
Примеры
Ввод 1 Ввод 2 Ввод 3
5 5 5
....X ..X.. ...X.
.OOOO ..... .....
..... OOOOO O.OOO
OOOO. ..... .....
@.... ..@.. ....@
Вывод 1 Вывод 2 Вывод 3
Y N Y
+++++ ..++.
+OOOO .++..
+++++ O+OOO
OOOO+ .++++
@++++ ....@
|
