Module: Gierige Algorithmen

Problem

Melone will seine neue Entwicklung testen, einen Roboter, der sich durch die Labyrinthe bewegen kann.
Roboter ist in einem rechteckigen Labyrinth von nx m. Jede der Labyrinthzellen ist entweder leer oder intakt.
Der Roboter kann sich zwischen der Seite der Käfige nach links bewegen (L-Symbol), rechts (R-Symbol), stromaufwärts (U-Symbol) oder unten (D-Symbol). Der Roboter kann sich nur in eine Zelle bewegen, wenn er leer ist. Der ursprüngliche Roboter ist in einer leeren Zelle.

Melona will, dass der Roboter den lexikographischen Mindestlängenzyklus genau k durchläuft, der beginnt und in der Zelle endet, in der sich der Roboter ursprünglich befindet. Roboter ist erlaubt, jede Zelle jederzeit zu besuchen (einschließlich der Startzelle).

Der Weg des Roboters liegt in einer Linie bestehend aus den Symbolen "L", "R", "U" und "D". Zum Beispiel, wenn der Roboter zuerst geht, dann links, dann rechts und oben, wird sein Weg als DLRU aufgezeichnet.

Hilfe Melone bestimmen, welcher Weg des Roboters dem lyxikographischen Mindestlängenzyklus genau k entspricht oder mir sagen, dass dies nicht existiert.

Eingabe:
Die erste Zeile folgt drei ganze Zahlen n, m und k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10⁶Abmessungen von Labyrinth und Zykluslänge.
Jede der folgenden n Linien folgt m Symbolen - Beschreibung des Labyrinths. Ist das Symbol " . " , ist die aktuelle Zelle leer. Ist das Symbol " , ist die aktuelle Zelle ein Hindernis. Ist das Symbol " X " , ist der Roboter in dieser Zelle, und es ist leer. Es ist garantiert, dass das Symbol " X " wieder auf das Labyrinth trifft.

Ausgangsdaten:
Lexikographisch entfernen Sie den minimalen Weg des Roboters der Länge genau k, der beginnt und endet in der Zelle, wo sich der Roboter ursprünglich befindet. Wenn es keine solche Route gibt, nehmen Sie IMPOSSIBLE heraus.

Beispiele:

Eingangsdaten	Ausgangsdaten
Artikel 2 ** X...	RL
5 6 14 *** X. ♪ ♪ ♪	DLDDLLRRRUURU
3 3 4 *** X ***	IMPOSSIB