#CF3A. Shortest path of the king(国王的最短路径)

Shortest path of the king(国王的最短路径)

题目描述

棋盘上只剩下国王一人。尽管孤独,他并不灰心,因为他有国家大事要做。例如,他要对广场tt进行正式访问。由于国王不习惯浪费时间,他想用最少的步数从目前的位置ss到达广场tt。帮助他做到这一点。

国王可以一次移动到与国王当前所在的正方形有共同边或共同顶点的正方形(通常他可以移动到88个不同的正方形)。第一行包含了方块s的棋盘坐标,第二行是方块tt。棋盘坐标由两个字符组成,第一个是小写拉丁字母(从a到h),第二个是1188的数字。在第一行打印nn-最小的国王走法个数。然后在第nn行打印这些招式本身。

每一步都用一个字母: LL, RR, UU, DD, LULU, LDLD, RURURDRDLLRRUUDD分别代表左右、上下移动(根据图片),22个字母组合代表对角线移动。如果答案不是唯一的,打印其中任何一个。

输入格式

第一行包含正方形ss的棋盘坐标,第二行包含正方形tt的坐标。棋盘坐标由两个字符组成,第一个是小写拉丁字母(从aahh),第二个是1188之间的数字。

输出格式

在第一行打印国王的最小移动次数nn。然后在第nn行打印这些招式本身。每一步都用一个88: LL, RR, UU, DD, LULU, LDLD, RURURDRDLLRRUUDD分别代表左右、上下移动(根据图片),22个字母组合代表对角线移动。如果答案不是唯一的,打印其中任何一个。

样例

a8
h1
7
RD
RD
RD
RD
RD
RD
RD