El Robot Imparable
Un grupo de estudiantes estaba desarrollando un robot que puede moverse en un laberinto. Sin embargo, el robot no es perfecto y no puede cambiar de dirección ni detenerse hasta que alcance una pared u otro obstáculo. Así que, una vez que el robot inicia su movimiento, tiene que llegar a la pared más cercana en la dirección en la que se está desplazando y, recién entonces, elegir una nueva dirección.
Se te pide determinar cuál es el número mínimo de movimientos necesarios para que el robot vaya desde la posición inicial
S hasta la posición final E, e imprimir los comandos que se deben enviarle para lograrlo:- L - moverse a la izquierda
- U - moverse hacia arriba
- R - moverse a la derecha
- D - moverse hacia abajo
Input
La primera línea de la entrada contiene dos números
h y w (2 ≤ h, w ≤ 100), que representan la altura y la anchura de la cuadrícula.Las siguientes
h líneas contienen w caracteres que describen la cuadrícula:.representa el piso
#representa una pared
Ses el punto de inicio
Ees el punto final
Se garantiza que la cuadrícula está rodeada por paredes para que el robot no pueda salirse de sus límites.
Output
El programa debe imprimir en la primera línea el número mínimo de movimientos para ir de la posición de inicio a la final. En la segunda línea, deben aparecer todos los comandos que se le enviarán al robot. Si hay varias soluciones posibles, el programa puede imprimir cualquiera de ellas.
Si es imposible para el robot llegar hasta el final, entonces el programa debe imprimir
Impossible.Ejemplos
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUSugerencia
Puedes tratar el punto de inicio como piso (
.) y el punto final como una pared (#).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB