Ваня рисует прямоугольник и разбивает его на M строк и N столбцов. Он заполняют некоторые ячейки монетками "Х". Две разные пустые ячейки заполняет человечком "Y" и сундуком "В". Человечек может передвигаться в соседнюю ячейку (соседними считаются ячейки, граничащие по стороне), а также человек может передвигать сундук для этого нужно встать в соседнюю к сундуку ячейку и толкнуть его от себя (сходит на ячейку к сундуку). При этом сундук передвинется на одну соседнюю ячейку в направлении, заданном толчком, а человечек переместится в ячейку, где только что находился клад. Все объекты должны быть внутри прямоугольника. В прямоугольнике могут остаться пустые ячейка ".". Задача человечка вытолкнуть клад из прямоугольника, выход из прямоугольника Ваня обозначает буквой "Т". Необходимо написать программу, которая определяет последовательность толчков и передвижений человечка, следуя которой сундук можно передвинуть к выходу (выход находится в пустой ячейке). Так как клад очень тяжелый, количество толчков должно быть минимальным. При наличии нескольких оптимальных последовательностей следует указать любую из них. Пример прямоугольника
. . Y
. B .
T X X
Формат входных данных
Первая строка содержит числа M и N . Следующие M строк содержат описание лабиринта. Каждая строка состоит из N символов, описывающих ячейки лабиринта: заполненная монетками ячейка обозначается латинской буквой "X", пустая ячейка обозначается символом "." (ASCII код 46), начальная позиция человечка — буквой "Y", начальная позиция сундука — латинской буквой "В", выход — латинской буквой "Т".
Формат выходных данных
Если решения не существует, то выводится "NO". Иначе, в первой строке выходного должно содержаться слово "YES", а во второй строке — последовательность символов, определяющая действия человечка, в частности, символы "w", "e", "n", "s" обозначают передвижения человечка на запад, восток, север и юг соответственно, а символы "W", "E", "N", "S" обозначают толчки человечка в соответствующих направлениях.
Пример ввода/вывода
Ввод Вывод
3 3 YES
..Y sWnwS
.B.
TXX
130
264
Ответы на вопрос:
Популярно: Информатика
-
анисенко11104.04.2021 00:59
-
aidosashimbek20029.07.2022 21:22
-
ksushakorovina127.06.2021 04:01
-
Ясныйпень27.09.2022 14:07
-
Христинияголовн23.03.2022 03:09
-
ашоттрубошот26.05.2022 09:14
-
Cfhbcbudh05.03.2023 23:35
-
mgvzvit200521.08.2020 02:11
-
anasgaliev13.06.2021 13:30
-
ольга172424.05.2023 12:28