有人用细笔画了一个大的正方形,内部被划分为 个单位方格。例如,当 时,图形如下所示:
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
你有一支粗笔。你将从这个网格的左上角出发,沿着已有的细网格线移动,描绘出一个恰好由 个单位方格组成的区域的边界。
我们用字母 U、D、L、R 分别表示笔向上、向下、向左、向右移动一个单位距离。
例如,对于 ,,一条可行的路径是 DDDRRRUULDLUUL。它描绘出以下面积为 的区域的边界:
+###+---+---+
# # | |
+---+---+###+
# # # #
+---+###+---+
# | | #
+###+###+###+
你的路径必须满足以下要求:
- 路径不能离开这个 的正方形:每一步都必须沿着已有的细网格线移动。
- 一个单位方格被视为你描绘的区域内部,当且仅当从大正方形的外部无法在不穿过你的路径的情况下到达它。
在所有恰好描绘出面积为 的区域的路径中,找出描述长度最短的路径并返回。如果有多个最优路径,你可以返回其中任意一个。