Неостановимый робот
Группа студентов разрабатывала робота, который может перемещаться в лабиринте. Однако у робота есть один недостаток: он не может изменить направление движения или остановиться, пока не упрётся в стену или другое препятствие. Значит, когда робот начинает движение по какому-то направлению, он обязательно доедет до ближайшей стены, а уже после этого сможет выбрать новое направление.
Необходимо определить, какое минимальное количество движений потребуется роботу, чтобы добраться от начальной позиции
S до конечной позиции E, и вывести последовательность команд, которые нужно отправить роботу для достижения этой цели:- L — движение влево
- U — движение вверх
- R — движение вправо
- D — движение вниз
Входные данные
В первой строке дана пара чисел
h и w (2 ≤ h, w ≤ 100) — высота и ширина сетки.Далее следует
h строк, каждая содержит w символов, описывающих лабиринт:.означает свободный пол
#означает стену
S— начальная точка
E— конечная точка
Гарантируется, что лабиринт окружён стенами, чтобы робот не мог выехать за его пределы.
Выходные данные
На первой строке выведите минимальное количество движений, необходимых для достижения конца. На второй строке укажите все команды, которые нужно отправить роботу. Если существует несколько путей, можно вывести любой из них.
Если добраться до конечной точки невозможно, выведите
Impossible.Примеры
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUПодсказка
В некоторых решениях можно рассматривать начальную точку как пол (
.) и конечную точку как стену (#).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB