28832번 - Поиски Трезубца 스페셜 저지다국어

Артур и Мера в поисках трезубца попали в запутанные катакомбы. Хорошо, что у Меры с собой есть карта. Из карты стало ясно, что комнаты в катакомбах имеют одинаковый размер и расположены в $n$ рядов по $m$ комнат в каждом. При этом комнаты, смежные по стороне, соединены проходами. Более того, с помощью своих суперсил Артур может проходить из комнат $n$-го ряда не только в комнаты $(n-1)$-го ряда, но и первого. То же самое касается и комнат из $m$-го столбца. Формально из любой комнаты с координатами ($i$, $j$) существует четыре перехода в комнаты с координатами:

1. ($i + 1$, $j$), если $i < n$, и ($1$, $j$) иначе.
2. ($i - 1$, $j$), если $i > 1$, и ($n$, $j$) иначе.
3. ($i$, $j + 1$), если $j < m$, и ($i$, $1$) иначе.
4. ($i$, $j - 1$), если $j > 1$, и ($i$, $m$) иначе.

Изначально Мера и Артур находятся в комнате ($1$, $1$). В некоторых комнатах спрятаны подсказки о местонахождении трезубца. Такие комнаты на плане помечены символом <<X>>. Героям нужно собрать их все, чтобы продолжить поиски. К сожалению, не все так просто. Расстоянием между двумя комнатами будем считать сумму абсолютных разностей их координат. Таким образом, расстояние между комнатами ($i_1$, $j_1$) и ($i_2$, $j_2$) можно вычислить по формуле $|i_1-i_2| + |j_1 - j_2|$.

Поиски подсказок осложнены тем, что комната с подсказкой откроется только тогда, когда собраны все подсказки из комнат со строго меньшим расстоянием до комнаты с координатами ($1$, $1$). То есть, если подсказки есть в комнатах ($1$, $2$) и ($2$, $3$), войти во вторую комнату можно только если первая комната уже была посещена.

Мера просит вас написать программу, которая составит маршрут по катакомбам таким образом, чтобы собрать все подсказки. Помогите героям!

В первой строке заданы два натуральных числа $n$ и $m$ --- размеры катакомб ($1\le n,m \le 100$).

В следующих $n$ строках дано описание комнат. На $j$-й позиции $i$-й из этих строк находится символ <<X>>, если в комнате ($i$, $j$) есть подсказка и <<.>>, если там пусто.

Исключением является первый символ первой строки, который всегда равен <<S>>. Он обозначает стартовую комнату, которая не содержит подсказок.

Выведите любую подходящую последовательность ходов обхода катакомб для поиска всех подсказок. На $i$-й позиции в последовательности должна быть буква:

• <<D>>, если нужно воспользоваться первым переходом.
• <<U>>, если нужно воспользоваться вторым переходом.
• <<R>>, если нужно воспользоваться третьим переходом.
• <<L>>, если нужно воспользоваться четвертым переходом.

Длина последовательности не должна превосходить $30\,000$.