Problem
Melone quiere probar su nuevo desarrollo: un robot que puede moverse a través de los laberintos.
El robot está en un laberinto rectangular de tamaño n × m. Cada una de las celdas del laberinto está vacía u ocupada por un obstáculo.
El robot puede moverse entre celdas adyacentes a la izquierda (símbolo "L"), derecha (símbolo "R", arriba (símbolo "U") o abajo (símbolo "D"). El robot solo puede moverse a una celda si está vacía. Inicialmente, el robot está en una jaula vacía.
Melone quiere que el robot pase por el ciclo lexicográficamente mínimo de longitud exactamente k, que comienza y termina en la celda donde se encuentra inicialmente el robot. El robot puede visitar cualquier celda cualquier cantidad de veces (incluida la inicial).
La ruta del robot está dada por una cadena que consta de los caracteres "L", "R", "U" y "D". Por ejemplo, si el robot primero baja, luego a la izquierda, luego a la derecha y hacia arriba, su ruta se escribe como "DLRU".
Ayuda a Melona a determinar qué camino del robot corresponde al ciclo lexicográficamente mínimo de longitud exactamente k, o dime que no existe tal cosa.
Entrada:
La primera línea va seguida de tres números enteros n, m y k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< /sup>) — dimensiones del laberinto y duración del ciclo.
Cada una de las siguientes n líneas contiene m caracteres — Descripción del laberinto. Si el símbolo es ".", entonces la celda actual está vacía. Si el símbolo es "*", entonces la celda actual está ocupada por un obstáculo. Si el símbolo es igual a "X", inicialmente el robot está en esta celda y está vacía. Se garantiza que el caracter "X" ocurre exactamente una vez en el laberinto.
Salida:
Imprima la ruta lexicográficamente mínima del Robot de longitud exactamente k, que comienza y termina en la celda donde se encuentra inicialmente el Robot. Si no existe tal ruta, imprima "IMPOSIBLE" (sin comillas).
Ejemplos:
| Entrada |
Salida |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
IMPOSIBLE |