Il Robot Inarrestabile
Un gruppo di studenti stava progettando un robot in grado di muoversi in un labirinto. Tuttavia, il robot non è perfetto: non può cambiare direzione né fermarsi finché non raggiunge un muro o un ostacolo. Così, nel momento in cui il robot inizia a muoversi, deve proseguire fino al primo ostacolo nella direzione intrapresa e solo allora può scegliere una nuova direzione.
L’obiettivo è determinare il numero minimo di mosse necessario affinché il robot passi dalla posizione di partenza
S a quella di arrivo E, e quindi stampare i comandi che gli studenti devono inviare al robot per riuscirci:- L - muoversi a sinistra
- U - muoversi in alto
- R - muoversi a destra
- D - muoversi in basso
Input
La prima riga dell’input contiene due numeri
h e w (2 ≤ h, w ≤ 100), che rappresentano l’altezza e la larghezza della griglia.Le successive
h righe contengono w caratteri che descrivono la griglia:.indica il pavimento
#indica un muro
Sè il punto di partenza
Eè il punto di arrivo
È garantito che l’intera griglia sia circondata da muri, impedendo al robot di uscire dal perimetro.
Output
Il programma deve stampare, sulla prima riga, il numero minimo di mosse che permetta al robot di passare dalla posizione di partenza a quella di arrivo. Sulla seconda riga, deve mostrare tutti i comandi necessari perché il robot completi il percorso. Se vi sono più soluzioni possibili, è sufficiente stamparne una qualsiasi.
Se non è possibile raggiungere la destinazione, il programma deve stampare
Impossible.Esempi
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUHint
Puoi trattare il punto di partenza come se fosse un pavimento (
.) e il punto di arrivo come se fosse un muro (#).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB