Problem
Melone は、彼の新しい開発、迷路を移動できるロボットをテストしたいと考えています。
ロボットは、サイズ n × m の長方形の迷路の中にいます。迷路の各セルは空であるか、障害物で占められています。
ロボットは、隣接するセル間を左 (シンボル "L")、右 (シンボル "R")、上 (シンボル "U") または下 (シンボル "D") に移動できます。ロボットは、セルが空の場合にのみセルに移動できます。最初、ロボットは空の檻の中にいます。
Melone は、ロボットが最初に配置されたセルで開始および終了する、正確に k の長さの辞書編集的に最小のサイクルをロボットが通過することを望んでいます。ロボットは任意のセルに何度でもアクセスできます (最初のセルを含む)。
ロボットのパスは、文字「L」、「R」、「U」で構成される文字列で指定されます。と「D」。たとえば、ロボットが最初に下に移動し、次に左に移動し、次に右に移動し、次に上に移動した場合、そのパスは「DLRU」と記述されます。
Melona がロボットのどの経路が辞書編集的に正確に k の長さの最小サイクルに対応するかを判断するのを手伝ってください。または、そのようなものは存在しないことを教えてください。
入力:
最初の行の後には、3 つの整数 n、m、k が続きます (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< / sup>) —迷路の寸法とサイクルの長さ。
次の n 行にはそれぞれ m 文字が含まれます —迷宮の説明。記号が「.」の場合、現在のセルは空です。記号が「*」の場合、現在のセルは障害物で占められています。シンボルが「X」に等しい場合、最初はロボットはこのセルにあり、空です。文字「X」迷路内で 1 回だけ発生します。
出力:
ロボットが最初に配置されたセルで開始および終了する、正確に k の長さのロボットの辞書式最小パスを出力します。そのようなパスが存在しない場合は、「IMPOSSIBLE」を出力します(引用符なし)。
例:
<本体>
| 入力 |
出力 |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
不可能 |