Pacman - Escapa a salvo
Estás jugando al juego Pacman. Te encuentras en un laberinto junto con algunos monstruos. Tu objetivo es llegar hasta una de las casillas en el borde del laberinto sin ocupar al mismo tiempo la misma casilla que un monstruo.
En cada turno, te mueves en alguna dirección (arriba, izquierda, derecha o abajo), y los monstruos también se desplazan en alguna dirección.
Si es posible escapar del laberinto con éxito, debes imprimir la ruta que puedes seguir. Ten en cuenta que esta estrategia debe funcionar incluso si los monstruos conocen tu plan.
Entrada
La primera línea de la entrada contiene dos números enteros
h y w (1 ≤ h, w ≤ 1000), que especifican la altura y la anchura del laberinto.Las siguientes
h líneas contienen w símbolos que describen el laberinto:.- piso
#- pared
M- monstruo
Y- tu posición inicial
Salida
La primera línea de la salida debe indicar cuántos pasos hacen falta para salir del laberinto, o
Impossible si no se puede lograr.Si es posible escapar, la segunda línea debe contener cualquier ruta válida que te permita conseguirlo.
Ejemplos
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB