Задача E. Lines
В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.
Ограничения: 2 <= N <= 40, время 1 с.
Ввод из файла lines.in. В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O
- шарик, @
- исходное положение шарика, который должен двигаться, латинской заглавной X
- конечное положение шарика.
Вывод в файл lines.out. В первой строке выводится 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+ .++++
@++++ ....@