2963. 表白机器人

单点时限: 2.0 sec

内存限制: 256 MB

永远不要以为 Matrix67 就是传说中的情圣。很少有人知道,Matrix67 竟然不好意思主动向 MM 表白!为此,Matrix67 派出他的表白机器人,帮他完成这一项光荣而艰巨的任务。
Matrix67 和 MM 所在的地方可以看作是一个封闭的平面空间,里面分成了 M x N 个房间,某些房间之间可能有墙。Matrix67 总在最左下角的那个房间,MM 总在最右上角的那个房间。Matrix67 需要给它的机器人输入一系列方向指令,控制机器人避开墙壁到达 MM 所在的位置。如果 L 表示向左移一格,R 表示向右移一格,U 表示向上移一格,D 表示向下移一格,那么在下图所示的 4x4 平面地图里,命令序列 RURUUR 可以让机器人从起点(左下角)到达终点(右上角)。
#---#---#---#---#
| | F |
# # # #---#
| | |
# # # #---#
| | |
# # # # #
| S |
#---#---#---#---#
但问题远远没有这么简单。由于设计上的缺陷,Matrix67 的机器人只能记忆 K 条指令。这就意味着,当机器人的行走路线过长时,指令不一定能完整地输入机器人。这怎么办呢?Matrix67 想到一个好办法:如果让机器人反复执行预先给定的 K 条指令,那么恰当的指令序列也能使机器人到达终点(虽然这样可能会走很多重复的路)。机器人会忽略所有命令它撞墙的指令。也就是说,如果下一个指令对应的方向上是一面墙的话,机器人将跳过该指令。Matrix67 希望知道,是否存在一个长度为 K 的命令序列,若机器人反复执行这段指令,最终会到达 MM 所在的地方。对于上面给出的例子,当 K=4 时,RRLU 是一个合法的答案。 【题目包含多组输入输出!】

输入格式

第一行输入四个用空格隔开的正整数 M、N、W 和 K,表示该平面区域内有 M 行 N 列小房间,房间与房间之间共有 W 面墙,Matrix67 需要给机器人输入的指令长度为 K。
以下 W 行每行四个数 Ai, Aj, Bi, Bj,表示第 Ai 行 Aj 列的房间与 Bi 行 Bj 列的房间之间有一面墙。
M,N<=5,K<=8。

输出格式

你的输出数据应该是一个由 L、R、U、D 四种字符组成的长度为 K 的字符串,表示一个合法的指令序列。机器人反复执行这串指令后最终可以到达右上角的房间。
输入数据保证有唯一解,因此你不用考虑多解或无解的情况。

样例

Input
4 4 5 4
1 2 1 3
2 2 2 3
1 4 2 4
2 4 3 4
3 1 3 2
Output
RRLU

8 人解决,9 人已尝试。

11 份提交通过,共有 28 份提交。

5.8 EMB 奖励。

创建: 7 年,9 月前.

修改: 2 年,5 月前.

最后提交: 4 年,4 月前.

来源: Matrix67

题目标签