Pacman - Uscire in Sicurezza
Stai giocando a Pacman. Ti trovi in un labirinto con alcuni mostri. Devi raggiungere una delle caselle sul bordo del labirinto senza mai condividere una casella con un mostro.
A ogni mossa, ti sposti in una direzione (su, sinistra, destra o giù), e anche i mostri si muovono in una direzione.
Se è possibile uscire dal labirinto incolume, dovresti stampare il percorso da seguire. La strategia deve funzionare anche se i mostri conoscono il tuo piano.
Input
La prima riga dell'input contiene due interi
h e w (1 ≤ h, w ≤ 1000), che indicano l'altezza e la larghezza del labirinto.Le successive
h righe contengono w simboli che descrivono il labirinto:.- pavimento
#- muro
M- mostro
Y- la tua posizione iniziale
Output
La prima riga dell'output deve contenere il numero di passi necessari per uscire dal labirinto, oppure
Impossible se non è possibile farlo.Se è possibile, la riga successiva deve contenere un qualunque percorso valido per farlo.
Esempi
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB