分数: 300 点
问题陈述
海豚位于二维笛卡尔平面中,正 x- 轴指向右且正 y- 轴朝上。
目前,他位于 (sx,sy)。在每一秒中,他可以向上、向下、向左或向右移动距离 1.
在这里, x- 和 y- 每次移动之前和之后的坐标必须是整数。
他将首先访问该点 (tx,ty) 其中 sx < tx 和 sy < ty,然后回到点 (sx,sy),然后访问该点
又 (tx,ty) ,最后回到正题 (sx,sy).
这里,在整个行程中,不允许他多次经过同一个点,除了以下点 (sx,sy) 和 (tx,ty).
在此条件下,为他找到一条最短路径。
约束
- -1000 ≤ sx < tx ≤ 1000
- -1000 ≤ sy < ty ≤ 1000
- sx,sy,tx 和 ty 是整数。
输入
输入由标准输入按以下格式给出:
sx sy tx ty
输出
打印字符串 S 代表 Dolphin 的最短路径。
的
树的 i- 第一个字符 S 应该对应于他的 i第一个动作。
运动方向应由以下字符表示:
U:向上D:向下L:左R:右
如果该条件下存在多条最短路径,则打印其中任意一条。
示例输入 1
0 0 1 2
示例输出 1
UURDDLLUUURRDRDDDLLU
一种可能的最短路径是:
- 从 (sx,sy) to (tx,ty) 第一次: (0,0) → (0,1) → (0,2) → (1,2)
- 从 (tx,ty) to (sx,sy) 第一次: (1,2) → (1,1) → (1,0) → (0,0)
- 从 (sx,sy) to (tx,ty) 第二次: (0,0) → (-1,0) → (-1,1) → (-1,2) → (-1,3) → (0,3) → (1,3) → (1,2)
- 从 (tx,ty) to (sx,sy) 第二次: (1,2) → (2,2) → (2,1) → (2,0) → (2,-1) → (1,-1) → (0,-1) → (0,0)
示例输入 2
-2 -2 1 1
示例输出 2
UURRURRDDDLLDLLULUUURRURRDDDLLDL