Problem
Melone quer testar seu novo desenvolvimento - um robô que pode se mover pelos labirintos.
O robô está em um labirinto retangular de tamanho n × m. Cada uma das células do labirinto está vazia ou ocupada por um obstáculo.
O robô pode se mover entre as células adjacentes para a esquerda (símbolo "L"), direita (símbolo "R", para cima (símbolo "U") ou para baixo (símbolo "D"). O robô só pode se mover para uma célula se ela estiver vazia. Inicialmente, o robô está em uma gaiola vazia.
Melone quer que o robô percorra o ciclo lexicograficamente mínimo de comprimento exatamente k, que começa e termina na célula onde o robô está inicialmente localizado. O robô pode visitar qualquer célula quantas vezes quiser (incluindo a inicial).
O caminho do robô é dado por uma string composta pelos caracteres "L", "R", "U" e "D". Por exemplo, se o robô primeiro desce, depois para a esquerda, depois para a direita e para cima, seu caminho é escrito como "DLRU".
Ajude Melona a determinar qual caminho do robô corresponde ao ciclo lexicograficamente mínimo de comprimento exatamente k, ou diga-me que tal coisa não existe.
Entrada:
A primeira linha é seguida por três inteiros n, m e k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< / sup>) — dimensões do labirinto e comprimento do ciclo.
Cada uma das próximas n linhas contém m caracteres — descrição do labirinto. Se o símbolo for ".", então a célula atual está vazia. Se o símbolo for "*", então a célula atual está ocupada por um obstáculo. Se o símbolo for igual a "X", inicialmente o robô está nesta célula e está vazio. É garantido que o caractere "X" ocorre exatamente uma vez no labirinto.
Saída:
Imprima o caminho lexicograficamente mínimo do Robô de comprimento exatamente k, que começa e termina na célula onde o Robô está inicialmente localizado. Se tal caminho não existir, imprima "IMPOSSÍVEL" (sem aspas).
Exemplos:
| Entrada |
Saída |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
IMPOSSÍVEL |