Back and Forth

题目描述

Dolphin 位于二维笛卡尔平面中，正 $x$ $-$ 轴向右，正 $y$ $-$ 轴向上。
目前，他位于点 $(sx,sy)$。每一秒，他可以向上、向下、向左或向右移动距离 $1$。
这里，移动前后 $x$ 和 $y$ 坐标都必须是整数。
他会先访问点 $(tx,ty)$，其中 sx < tx 且 sy < ty，然后返回到点 $(sx,sy)$，然后再访问点 $(tx,ty)$，最后返回到点 $(sx,sy)$。
在整个行程中，除点 $(sx,sy)$ 和 $(tx,ty)$ 外，他不被允许经过同一个点超过一次。
在此条件下，寻找一条最短路径。

输入格式

输入从标准输入给出，格式如下： $sx$ $sy$ $tx$ $ty$

输出格式

输出一个字符串 $S$，表示 Dolphin 的一条最短路径。
字符串 $S$ 的第 $i$ 个字符应对应他第 $i$ 次移动。
移动方向应由以下字符表示：

$U$: 向上 $D$: 向下 $L$: 向左 $R$: 向右

如果在该条件下存在多条最短路径，输出其中任意一条。

0 0 1 2

UURDDLLUUURRDRDDDLLU

-2 -2 1 1

UURRURRDDDLLDLLULUUURRURRDDDLLDL

提示

-1000 ≤ sx < tx ≤ 1000 -1000 ≤ sy < ty ≤ 1000 $sx,sy,tx$ 和 $ty$ 是整数。一种可能的最短路径为：

第一次从 $(sx,sy)$ 到 $(tx,ty)$：$(0,0)$ → $(0,1)$ → $(0,2)$ → $(1,2)$ 第一次从 $(tx,ty)$ 到 $(sx,sy)$：$(1,2)$ → $(1,1)$ → $(1,0)$ → $(0,0)$ 第二次从 $(sx,sy)$ 到 $(tx,ty)$：$(0,0)$ → $(-1,0)$ → $(-1,1)$ → $(-1,2)$ → $(-1,3)$ → $(0,3)$ → $(1,3)$ → $(1,2)$ 第二次从 $(tx,ty)$ 到 $(sx,sy)$：$(1,2)$ → $(2,2)$ → $(2,1)$ → $(2,0)$ → $(2,-1)$ → $(1,-1)$ → $(0,-1)$ → $(0,0)$

标签: AtCoder|abc051C

来源

AtCoder|abc051C