- Описание
- Отправленные решения
2. Спидран по Pac-Man
Недавно Федя стал победителем всероссийской олимпиады, проходившей в офисе 1C в Москве, и ему выплатили большую премию. Он не знал, куда ее потратить, поэтому решил скупать редкие устройства и пытаться пройти на них новейшие компьютерные игры. И вот недавно 1C gaming выпустила игру под названием «Сибирском Pac-Man» для устройств, совместимых с Siemens SL45. Потратив половину премии на покупку раритетного устройства в рабочем состоянии, Федя поставил игру и приступил к делу. Дело в том, что Федя $-$ спидраннер, то есть он занимается скоростным прохождением видеоигр. Федя, конечно же, и сам мог придумать оптимальную стратегию для прохождения этой игры, но он занят просмотром «Милого во Франксе».
В «Сибирском Pac-Man» игрок управляет Pac-Man $-$ главным героем, который изначально находится в левой верхней клетке прямоугольного поля размером $r \times c$ клеток, в каждой из которых находится по одной точке. Pac-Man должен съесть все точки, после чего прийти в клетку, лежащую в $a$-й строке и $b$-м столбце, на этом игра и закончится. Если хотя бы раз за игру Pac-Man побывает в какой-то клетке, то он автоматически съест точку, в ней находящуюся. Требуется вывести строку, состоящую из символов ‘U’, ‘L’, ‘D’, ‘R’, обозначающую последовательность ходов, которые должен совершить Pac-Man для того, чтобы пройти игру. Эта строка должна иметь минимально возможную длину.
Символ ‘U’, обозначает, что Pac-Man должен переместиться в клетку, которая находится над клеткой, в которой он сейчас находится, ‘D’ обозначает переход вниз, ‘L’ $-$ влево, ‘R’ $-$ вправо. Строки нумеруются сверху-вниз, а столбцы $-$ слева-направо. Нумерация строк и столбцов начинается с единицы, так что стартовая клетка имеет номер строки и столбца, равный 1.
Формат ввода
В первой строке задано единственное число $t$ ($1 \leq t \leq 600$) -- количество наборов входных данных.
В каждой из последующих $t$ строк задан один тестовый пример, состоящий из четырёх целых чисел $r$ и $c$ ($2 \leq r, c \leq 5000$), а потом $a$ и $b$ ($1 \leq a \leq r$, $1 \leq b \leq c$, $a \cdot b \ne 1$).
Так же гарантируется, что сумма значений $r \cdot c$ по всем входным данным не превосходит $3 \cdot 10^6$.
Формат вывода
Для каждого набора данных в отдельной строке выведите строку, состоящую из символов ‘U’, ‘L’, ‘D’, ‘R’, записанную без пробелов $-$ ответ на задачу. Если вариантов ответа несколько, выведите любой.
Ограничения
Ограничение времени
2 с
Ограничение памяти
512 МБ
Пример 1
2
3 3 2 2
2 2 1 2
RRDDLLUR
DRU
Пример 2
1
2 3 1 3
DRRULR