机器人位于一个大小为 n × m 的矩形迷宫中。迷宫的每个单元格要么是空的,要么被障碍物占据。机器人可以在左(符号“L”)、右(符号“R”)、上(符号“U”)或下(符号“D”)的相邻单元之间移动。仅当单元格为空时,机器人才能移动到该单元格。最初,机器人位于空单元格中。
你的任务是找到字典顺序上最小的机器人循环,其长度恰好为 k,其开始和结束于机器人最初所在的单元格。允许机器人多次访问任何单元格(包括启动)。
考虑机器人的路线是由符号“L”、“R”、“U”和“D”组成的线。例如,如果机器人先向下,然后向左,然后向右,向上,则意味着他的路线写为“DLRU”。
在此任务中,您不需要最小化路径的长度。找到满足上述要求的最小字典顺序(按字典中的字母顺序)。
输入
第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — 迷宫的大小和循环的长度。
以下 n 行每行包含 m 个符号——迷宫的描述。如果该符号等于“.”当前单元格为空。如果符号等于“*”,则当前单元格被障碍物占据。如果符号等于“X”,则机器人最初位于此单元格中,并且它是空的。保证在迷宫中只找到符号“X”一次。
输出
打印字典顺序最小的 Robot 路径,其长度恰好为 k,其开始和结束于最初 Robot 所在的单元格。如果没有这样的方式,则打印“IMPOSSIBLE”(不带引号)。
示例
输入 #1
2 3 2 .** X..
输出 #1
RL
输入 #2
5 6 14 ..***. *...X. ..*... ..*.** ....*.
输出 #2
DLDDLLLRRRUURU
输入 #3
3 3 4 *** *X* ***
输出 #3
IMPOSSIBLE
注意
在第一个示例中,长度为 2 的机器人存在两种循环方式 —“UD”和“RL”。第二个周期按词典顺序排列较少。
在第二个示例中,机器人应按以下方式移动:下、左、下、下、左、左、左、右、右、右、上、上、右、上。
在第三个示例中,机器人无法移动到相邻的单元格,因为它们被障碍物占据。