Курсор на буквенной клавиатуре

Средняя

На экране телевизора буквы расположены сеткой:


a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z

Курсор стоит на a (строка 0, столбец 0). Пульт умеет: U, D, L, R — сдвинуть курсор на клетку вверх, вниз, влево или вправо (только на клетку с буквой), и ! — ввести букву под курсором. Верните строку нажатий, которая вводит слово word за наименьшее число нажатий. Чтобы ответ был однозначным, при переходе к очередной букве нажимайте сначала все нужные L, затем U, затем R, затем D, и только потом !. Такой порядок никогда не выводит курсор за пределы сетки.

Пример 1

word="bug" → 'R!LDDDD!UUUR!'

b правее старта: R!. До u (строка 4, столбец 0): L, затем DDDD. До g (строка 1, столбец 1): UUU, затем R.

Пример 2

word="zoo" → 'DDDDD!UUURRRR!!'

z прямо под стартом: DDDDD!. До o (строка 2, столбец 4): сначала вверх UUU, потом вправо RRRR. Вторая o — просто ещё один !.

Пример 3

word="ya" → 'RRRRDDDD!LLLLUUUU!'

Ограничения

1 ≤ len(word) ≤ 100
word состоит из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Hash Table String

Вход

word="bug"

Ожидается

'R!LDDDD!UUUR!'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 104 теста на сервере, включая скрытые.