题目：Shortest path of the king | JXNUOJ

翻译：

Shortest path of the king

1000ms 65536K

描述：

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.

国王被独自留在棋盘上。尽管如此孤独，他没有灰心，因为他有事关国家的大事。例如，他必须正式访问t广场。由于国王没有浪费时间的习惯，他希望用最少的步数从当前的位置走到正方形。帮帮他吧！！。

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).

在一次移动中，国王可以到达与国王当前所在的正方形有公共边或公共顶点的正方形(通常有8个不同的正方形可以移动)。

输入：

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.

第一行包含正方形s的棋盘坐标，第二行-正方形t的坐标。棋盘坐标由两个字符组成，第一个是小写拉丁字母(a ~ h)，第二个是数字1 ~ 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.

在第一行输出n -国王的最小移动数。然后在n行中打印动作本身。每一个动作都描述为8:L, R, U, D, LU, LD, RU或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.

L、R、U、D分别代表左、右、上、下(如图)，2个字母组合代表对角线移动。如果答案不是唯一的，输出它们中的任何一个。

样例输入：

a8
h1

样例输出：

7
RD
RD
RD
RD
RD
RD
RD