CF769C Cycle In Maze

机器人位于一个大小为 $n \times m$ 的矩形迷宫中。迷宫的每个格子要么为空，要么被障碍物占据。机器人可以向左（符号 "L"）、右（符号 "R"）、上（符号 "U"）或下（符号 "D"）移动到相邻格子，只有该格子为空时才能移动。最初，机器人位于一个空格子。 你的任务是找到字典序最小、长度恰好为 $k$ 的机器人的环路，要求该环路起点和终点都在机器人最初所在的格子。机器人可以多次经过任意格子（包括起点）。 机器人的路径以仅包含 "L"、"R"、"U"、"D" 的字符串给出。例如，如果机器人首先向下走，然后向左，再向右，最后向上，其路径可表示为 "DLRU"。 本题不要求最短路径的长度，只需求出字典序最小（按字母顺序即字典顺序）的满足条件的路径。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq 10^{6}$），分别表示迷宫的大小和路径长度。 接下来的 $n$ 行，每行包含 $m$ 个字符，表示迷宫的情况。如果字符为 "."，表示该格子为空；如果为 "*"，表示该格子为障碍物；如果为 "X"，表示机器人初始时在该空格子。保证 "X" 在迷宫中恰好出现一次。

输出机器人的一个字典序最小、长度恰好为 $k$ 的路径，该路径起点和终点均为机器人初始所在的格子。如果不存在这样的路径，输出 "IMPOSSIBLE"（不带引号）。

在第一个样例中，存在两条长度为 $2$ 的环路——"UD" 和 "RL"。第二条在字典序上更小。 在第二个样例中，机器人的移动方式应为：下、左、下、下、左、左、左、右、右、右、上、上、右、上。 在第三个样例中，机器人无法移动到相邻格子，因为都被障碍物阻挡。 由 ChatGPT 5 翻译