CF3A 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` 代表向右上方移动）。如果答案不唯一，请输出任意一个答案。