| Codeforces Beta Round 3 |
|---|
| Закончено |
Одинокий король остался совсем один на шахматной доске. Несмотря на одиночество, он вовсе не унывает — ведь ему еще надо сделать так много дел государственной важности. Например, ему надо совершить официальный визит в клетку t. Так как король не привык терять попусту время, он хочет добраться от своего местоположения s до клетки t за наименьшее число ходов. Помогите ему это сделать.
Король за один ход может переместиться на любую клетку, которая по стороне или углу граничит с текущей (их в общем случае 8).
В первой строке входных данных заданы шахматные координаты клетки s, а во второй — клетки t.
Шахматные координаты состоят из двух символов, один из которых это строчная буква латинского алфавита (от a до h), а второй — цифра от 1 до 8.
В первую строку выведите n — минимальное число ходов короля. Далее в n строк выведите сами ходы. Каждый ход описывается одной из восьми строк: L, R, U, D, LU, LD, RU или RD.
L, R, U, D, соответственно, означают ходы влево, вправо, вверх и вниз (согласно рисунку), двухбуквенные обозначения соответствуют диагональным ходам. Если решений несколько, выведите любое.
a8
h1
7
RD
RD
RD
RD
RD
RD
RD
