#P18089. Yesterday Once More (Easy Version)
Yesterday Once More (Easy Version)
题目描述
Yuki 生活在一个有 行、 列的网格中。行从上到下依次编号为 ,列从左到右依次编号为 。用 表示第 行、第 列的格子。
网格中共有 个障碍物,并且满足:
- 第 行和第 行没有障碍物。
- 对所有 ,第 行恰好有一个障碍物。
- 对所有 ,第 列至多有一个障碍物。
开始时,Yuki 位于 。她听说第 行生活着一群袋鼠,因此想前往第 行看风景。
Yuki 可以按给定指令移动。每条指令指定上、下、左、右中的一个方向,她尝试沿该方向移动一格:
- 如果目标格子在网格内且没有障碍物,就移动到目标格子;
- 否则,这次移动无效,Yuki 留在原地。
遗憾的是,Yuki 不知道障碍物的具体位置,只知道上面的三条摆放规则。
请构造一串固定的移动指令,使得对于任意一种满足条件的障碍物分布,Yuki 在执行这一整串指令的过程中,至少有一次到达第 行。
注意:只要求她在某个时刻到达过最后一行,不要求执行完全部指令后仍停留在那里。
简单版要求指令总数不超过 。
输入格式
输入只有一行,包含一个整数 。
输出格式
第一行输出整数 ,表示指令总数,要求满足 。
第二行输出一个长度恰好为 的字符串 ,仅包含以下四种字符:
| 字符 | 操作 |
|---|---|
U |
向上移动一格 |
D |
向下移动一格 |
L |
向左移动一格 |
R |
向右移动一格 |
如果有多个符合要求的答案,输出任意一个即可。
数据范围
对于所有测试数据,。
样例 1
输入
2
输出
4
DRDD
样例 2
输入
3
输出
17
DDDUUURDDDUUURDDD
样例解释
在样例 1 中,网格为 ,只有第 行有一个障碍物,因此仅有两种合法摆法。用 # 表示障碍物,用 . 表示空格:
情况一:
..
#.
..
执行 DRDD 时,Yuki 依次位于
情况二:
..
.#
..
执行 DRDD 时,Yuki 依次位于
两种情况下都能到达第 行,所以这个答案合法。
样例 2 中,共有 种合法障碍物分布;给出的指令序列在这六种情况下均能到达第 行。