CF317E Princess and Her Shadow

公主 Vlada 喜欢在草地上跳跃，也喜欢在森林里散步。一天——一个美丽而晴朗的日子——在散步途中，公主惊讶地发现她的影子不见了！“天哪！”，她想着，开始在森林里寻找自己的影子。 通常影子非常懒惰，只会躺在公主的脚下睡觉。但在这个异常炎热的夏日，影子厌倦了这种无聊的生活，于是决定和 Vlada 玩一场游戏。 这个故事发生的森林可以看作平面上的若干整数格点集，在这里，影子和公主每次只能向上、下、左、右四个方向之一移动 $1$ 格。有些格子长着树（就像一片美丽的森林那样）。影子和公主都不能进入有树的格子。不幸的是，这片森林正经历艰难时期，所以其实只有很少几棵树…… 一开始，公主站在 $(v_x, v_y)$ 这个格子，而影子藏在 $(s_x, s_y)$，公主、影子以及所有树的位置各不相同。 影子和公主玩游戏。每当公主朝某一方向移动一格时，影子也会同时尝试朝同一方向移动一格（如果目的格子没有树）；否则，影子保持不动。影子非常“幽灵”，两个人不会互相阻碍。 当某一步移动后，公主和影子位于同一格子时，就称影子被公主“抓住”。Vlada 最终成功抓住了她的影子！你能做到吗？

输入的第一行为 $v_x$、$v_y$、$s_x$、$s_y$ 和树的数量 $m$（$0\leq m\leq 400$）。 接下来的 $m$ 行，每行包含一棵树的坐标。 所有坐标均为 $-100$ 到 $100$ 之间的整数。公主、影子和树的位置互不相同。

如果公主无法抓住影子，输出“-1”。 否则，输出一段仅由字符 “L”、“R”、“D”、“U” 组成的操作序列，代表公主的每一步行动（L — 向左移动，R — 向右，U — 向上，D — 向下，$x$ 轴向右，$y$ 轴向上）。 操作序列长度不能超过 $10^6$。所有移动都必须合法，即不能进入有树的格子。允许在最后一步之前，公主和影子已经处于同一格。

下图为样例的示意图（公主、影子与树分别为粉色、灰色与黑色，蓝点表示格点中心）。 在第一个样例中，公主可以向左走两步、再向上一步，然后向右一步： 在第二个样例中，公主无法抓住影子： 在第三个样例中，公主可以向左走两步，再向下走一步（顺序随意）： 由 ChatGPT 5 翻译