Задача E. Lines (2)
В таблице из 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+ .++++
@++++ ....@
|
