← 返回题目列表

AtCoder · abc051_c

C. 来回

中文机器翻译题面 查看原题

分数: 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