Технокубок 2016 - Отборочный Раунд 1 |
---|
Finished |
Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой что:
Ниже изображены несколько примеров допустимых циклов:
Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.
В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:
Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).
Найдите искомую последовательность команд, допускается любое направление обхода цикла.
В первой строке входных данных записаны два целых числа n и m (3 ≤ n, m ≤ 100) — количество строк и столбцов прямоугольного клетчатого поля соответственно.
В следующих n строках записаны по m символов, каждый из которых — «.», «*» или «S». Гарантируется, что отличные от «.» символы образуют цикл без самопересечений и самокасаний. Также гарантируется, что на поле ровно одна клетка содержит «S» и что она принадлежит циклу. Робот не может посещать клетки, помеченные символом «.».
В первую строку выходных данных выведите искомую последовательность команд для Робота. Направление обхода цикла Роботом может быть любым.
3 3
***
*.*
*S*
LUURRDDL
6 7
.***...
.*.*...
.*.S**.
.*...**
.*....*
.******
UULLDDDDDRRRRRUULULL
В первом тестовом примере для обхода по часовой стрелке последовательность посещенных роботом клеток выглядит следующим образом:
Name |
---|