printРабочее место участника

printЗадачи

54. Lines

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В таблице из `N` строк и `N` столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.
Ввод
В первой строке находится число `N` (`2\ ≤\ N\ ≤\ 250`), в следующих `N` строках – по `N` символов. Символом точки обозначена свободная клетка, латинской заглавной O – шарик, @ – исходное положение шарика, который должен двигаться, латинской заглавной X – конечное положение шарика.
Вывод
В первой строке выводится "Y", если движение возможно, или "N", если нет. Если движение возможно, далее следует `N` строк по `N` символов – как и на вводе, но буква X, а также все точки по пути заменяются плюсами.

Пример ввода 1

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

Пример вывода 1

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

Пример ввода 2

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

Пример вывода 2

N

Пример ввода 3

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

Пример вывода 3

Y    
..++.
.++..
O+OOO
.++++
....@
Источник: Меньшиков
loading