← 返回题目列表

Codeforces · 317/E

E. 公主和她的影子

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

弗拉达公主喜欢在草地上跳跃和在森林里散步。有一天——美好的、阳光明媚的一天——公主在散步时惊讶地发现她的影子不见了! “天哪!”——她想道,然后开始寻找森林里的影子。

通常情况下,影子太懒了,只是睡在公主下面。但在这个炎热的夏天,她厌倦了这样平淡的生活,所以她决定和弗拉达一起玩。

森林,我们的角色自娱自乐的地方,可以被表示为平面中的一组整数单元,其中影子和公主只能向上、向下、向左和向右移动 1。一些单元(就像在像样的森林中发生的那样)被树木占据。影子和公主不允许进入有树的牢房。不幸的是,现在正是森林的艰难时期,所以这里生长的树木很少......

起初,公主在牢房 (vx, vy) 内行走,而影子则躲在牢房 (sx, sy) 中躲避公主。公主、影子和树木位于不同的牢房中。

影子正在和公主玩耍。一旦公主向某个方向移动 1,如果可能的话,影子会同时向同一方向飞行 1(如果要飞向的单元格没有被某棵树占据);否则,影子就不会移动。阴影非常阴暗,所以我们的角色不会互相干扰。

如果经过一些移动后,影子和公主都位于同一个牢房中,我们就说影子被公主抓住了。弗拉达成功抓住了她的影子!你可以吗?

输入

输入的第一行包含字符 vx、vy、sx、sy 的坐标和树的数量 m (0 ≤ m ≤ 400)。接下来的 m 行包含树木的坐标。

所有坐标均为 -100 到 100 之间的整数(包含 -100 和 100)。公主、影子和树木位于不同的牢房中。

输出

如果公主不可能抓住影子,则打印“-1”(不带引号)。

否则打印一系列字符“L”,“R”,“D”,“U”,对应于公主的移动,随后她将能够在某个回合抓住影子(L - 向左移动,R - 向右,U - 向上,D - 向下;x 轴指向右侧,y - 向上)。

字符数(即步数)不得超过106个。公主的所有步法必须正确,即不能通向长有树的单元格。在最后一轮之前,公主和影子可以占据同一个牢房。

示例

输入 #1

0 0 1 0 1
0 1

输出 #1

LLUR

输入 #2

5 0 3 0 8
2 -1
2 0
2 1
3 -1
4 1
4 0
3 1
4 -1

输出 #2

-1

输入 #3

3 2 1 1 3
0 1
1 0
0 0

输出 #3

DLL

注意

下面给出了样本的图片(公主、影子和树木分别用粉红色、灰色和黑色着色;蓝点标记了格子中心)。

在第一种情况下,公主可以向左迈两步,向上迈一步,向右迈一步:

在以下情况下,公主无法捕捉到影子:

在最后一个示例中,公主可以向左迈两步,向下迈一步(以任何顺序):