← 返回题目列表

Codeforces · 648/C

C. 路径作业

中文机器翻译题面 查看原题

给定一个由 n 行和 m 列组成的矩形方格字段。该字段包含一个“*”字符循环,例如:

- 通过访问每个单元格一次,每次向上/向下/向右/向左移动一个单元格,可以绕过该循环;
- 循环不包含自相交和自接触,即循环的两个单元在一侧相邻当且仅当它们沿循环移动时相邻(也禁止在拐角处自接触)。

以下是有效循环的一些示例:

除循环之外的字段的所有单元格都包含符号“.”。场上正好有一个周期。机器人不允许访问除循环之外的单元。

循环的其中一个单元中有一个机器人。该单元格标有符号“S”。找到机器人的一系列命令来绕过循环。四个可能的命令中的每一个都由一个字母编码,并通过一个单元指示机器人的移动:

- “U” — 向上移动一个单元格,
- “R” - 向右移动一个单元格,
- “D” - 向下移动一个单元格,
- “L” - 向左移动一个单元格。

机器人必须绕一圈,访问每个单元格一次(起点除外 - 它的路径开始和结束的地方)。

找到所需的命令序列,允许任何方向遍历循环。

输入

输入数据的第一行包含两个整数 n 和 m (3 ≤ n, m ≤ 100) — 分别是矩形方格域的行数和列数。

接下来的 n 行包含 m 个字符,每个字符是“.”、“*”或“S”。保证除了“.”之外。这些符号形成一个循环,没有自相交或自接触。还可以保证场上恰好有一个单元格包含“S”并且它属于一个循环。机器人无法访问标有“.”的单元格。象征。

输出

在输出的第一行中,打印机器人所需的命令序列。机器人遍历循环的方向可以是任意方向。

示例

输入 #1

3 3
***
*.*
*S*

输出 #1

LUURRDDL

输入 #2

6 7
.***...
.*.*...
.*.S**.
.*...**
.*....*
.******

输出 #2

UULLDDDDDRRRRRUULULL

注意

在第一个顺时针遍历的测试用例中,机器人访问的单元格顺序如下:

1.细胞(3, 2);
2.细胞(3, 1);
3.细胞(2, 1);
4. 细胞 (1, 1);
5. 细胞(1, 2);
6. 细胞 (1, 3);
7. 细胞 (2, 3);
8. 细胞 (3, 3);
9. 单元格 (3, 2)。