Shortest path of the king

题意翻译

国王独自一人在国际象棋棋盘上。尽管他很孤独，但他并不会灰心，因为他有国家大事要做。例如，他必须对方格 $t$ 进行访问。因为国王没有浪费时间的习惯，所以他想从目前的位置（方格 $s$）上出发，走最少的步数。请你帮他做这件事。 在一次移动中，国王可以到达与他目前所在方格有共同的边或共同的顶点的方格里（通常情况下，他可以移动到 $8$ 个不同的方格里）。 **【输入格式】** 第一行包含方格 $s$ 的棋盘坐标，第二行包含方格 $t$ 的棋盘坐标。 棋盘坐标由两个字符组成，第一个是从 `a` 到 `h` 的小写拉丁字母，第二个是从 `1` 到 `8` 的数字。具体情况如上图所示。 **【输出格式】** 在第一行输出 $n$——国王移动的最小步数。然后接下来 $n$ 行输出移动的每一步。每次移动用 `L`、`R`、`U`、`D`、`LU`、`LD`、`RU` 或 `RD` 中的一个来描述。 `L`、`R`、`U`、`D` 分别指向左、向右、向上和向下移动，两个字母的组合代表沿着对角线移动（如 `RU` 代表向右上方移动）。如果答案不唯一，请输出任意一个答案。

题目描述

The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, because he has business of national importance. For example, he has to pay an official visit to square $ t $ . As the king is not in habit of wasting his time, he wants to get from his current position $ s $ to square $ t $ in the least number of moves. Help him to do this. In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).

输入输出格式

输入格式

The first line contains the chessboard coordinates of square $ s $ , the second line — of square $ t $ . Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1 to 8.

输出格式

In the first line print $ n $ — minimum number of the king's moves. Then in $ n $ lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD. L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.

输入输出样例

输入样例 #1

a8
h1

输出样例 #1

7
RD
RD
RD
RD
RD
RD
RD