logo AlgoBeat OnlineJudge 返回比赛
登录 注册

E. [TopCoder SRM 855] SurroundArea(暂无 SPJ)

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

有人用细笔画了一个大的正方形,内部被划分为 个单位方格。例如,当 时,图形如下所示:

    +---+---+---+
    |   |   |   |
    +---+---+---+
    |   |   |   |
    +---+---+---+
    |   |   |   |
    +---+---+---+

你有一支粗笔。你将从这个网格的左上角出发,沿着已有的细网格线移动,描绘出一个恰好由 个单位方格组成的区域的边界。

我们用字母 UDLR 分别表示笔向上、向下、向左、向右移动一个单位距离。

例如,对于 ,一条可行的路径是 DDDRRRUULDLUUL。它描绘出以下面积为 的区域的边界:

    +###+---+---+
    #   #   |   |
    +---+---+###+
    #   #   #   #
    +---+###+---+
    #   |   |   #
    +###+###+###+

你的路径必须满足以下要求:

  • 路径不能离开这个 的正方形:每一步都必须沿着已有的细网格线移动。
  • 一个单位方格被视为你描绘的区域内部,当且仅当从大正方形的外部无法在不穿过你的路径的情况下到达它。

在所有恰好描绘出面积为 的区域的路径中,找出描述长度最短的路径并返回。如果有多个最优路径,你可以返回其中任意一个。

输入格式

第一行包含一个整数
第二行包含一个整数

输出格式

一个字符串,表示描绘出指定区域的最短路径,由字符 UDLR 组成。

样例

样例 #1

样例输入 #1

3
6

样例输出 #1

DDDRRUUULL

样例解释 #1

与题目描述中一样,,需要描绘面积为 的区域。题目描述中展示的路径并不是最优的——直接画一个 的矩形更优。


样例 #2

样例输入 #2

5
24

样例输出 #2

RRRRDRDDDDLLLLLUUUUU

样例解释 #2

该路径省略了右上角的那个单位方格。


样例 #3

样例输入 #3

4
13

样例输出 #3

DDRDRDRRUUUULLLL

样例解释 #3

路径描绘了如下区域边界:

    +###+###+###+###+
    #   |   |   |   #
    +---+---+---+---+
    #   |   |   |   #
    +###+---+---+---+
    |   #   |   |   #
    +---+###+---+---+
    |   |   #   |   #
    +---+---+###+###+

还有很多其他的最优路径,其中一些描绘出的形状与上图在几何上并不完全相同。

数据范围与提示

  • 你的路径不一定需要回到起点。
  • 笔可以多次经过同一条网格线段。该线段始终被视为已被描绘(无论笔经过它多少次)。
  • 虽然上述两种操作是允许的,但如果你的目标是最小化路径长度,你可以自行判断它们是否有用。

数据范围