Problem
Melone veut tester son nouveau développement - un robot qui peut se déplacer dans les labyrinthes.
Le robot se trouve dans un labyrinthe rectangulaire de taille n×&minsp;m. Chacune des cellules du labyrinthe est soit vide, soit occupée par un obstacle.
Le robot peut se déplacer entre les cellules adjacentes vers la gauche (symbole "L"), la droite (symbole "R", le haut (symbole "U") ou le bas (symbole "D"). Le robot ne peut se déplacer vers une cellule que si celle-ci est vide. Initialement, le robot est dans une cage vide.
Melone veut que le robot passe par le cycle lexicographiquement minimum de longueur exactement k, qui commence et se termine dans la cellule où se trouve initialement le robot. Le robot est autorisé à visiter n'importe quelle cellule autant de fois que nécessaire (y compris celle de départ).
La trajectoire du robot est donnée par une chaîne composée des caractères "L", "R", "U" et "D". Par exemple, si le robot descend d'abord, puis à gauche, puis à droite et en haut, alors son chemin est écrit comme "DLRU".
Aidez Melona à déterminer quelle trajectoire du robot correspond au cycle lexicographiquement minimum de longueur exactement k, ou dites-moi que cela n'existe pas.
Saisie :
La première ligne est suivie de trois entiers n, m et k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< /sup>) — dimensions du labyrinthe et durée du cycle.
Chacune des n lignes suivantes contient m caractères — description du labyrinthe. Si le symbole est ".", la cellule actuelle est vide. Si le symbole est "*", alors la cellule courante est occupée par un obstacle. Si le symbole est "X", alors initialement le robot est dans cette cellule, et elle est vide. Il est garanti que le caractère "X" se produit exactement une fois dans le labyrinthe.
Sortie :
Imprimer le chemin lexicographiquement minimal du Robot de longueur exactement k, qui commence et se termine dans la cellule où se trouve initialement le Robot. Si un tel chemin n'existe pas, imprimez "IMPOSSIBLE" (sans les guillemets).
Exemples :
| Entrée |
Sortie |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DDDLLLRRRUURU |
3 3 4
***
*X*
*** |
IMPOSSIBLE |