Der Unaufhaltsame Roboter
Eine Gruppe von Studierenden entwickelte einen Roboter, der sich in einem Labyrinth bewegen kann. Allerdings ist der Roboter nicht perfekt und kann seine Richtung nicht ändern oder anhalten, bevor er eine Wand oder ein Hindernis erreicht. Sobald er sich in Bewegung setzt, fährt er also bis zur nächstgelegenen Wand in seiner aktuellen Richtung und wählt dann eine neue Bewegungsrichtung.
Ihr Auftrag ist es herauszufinden, wie viele Züge der Roboter mindestens benötigt, um von der Startposition
S zur Endposition E zu gelangen. Anschließend sollen Sie die Befehle ausgeben, die an den Roboter gesendet werden müssen, damit er sein Ziel erreicht:- L – Bewegung nach links
- U – Bewegung nach oben
- R – Bewegung nach rechts
- D – Bewegung nach unten
Eingabe
Die erste Zeile der Eingabe enthält zwei Zahlen
h und w (2 ≤ h, w ≤ 100), die die Höhe und Breite des Gitters angeben.Die nächsten
h Zeilen enthalten w Zeichen, die das Gitter beschreiben:.ist der Boden
#ist eine Wand
Sist der Startpunkt
Eist der Zielpunkt
Es ist sichergestellt, dass das Gitter von Wänden umgeben ist, damit der Roboter es nicht verlassen kann.
Ausgabe
Das Programm soll in der ersten Zeile die minimale Anzahl von Zügen ausgeben, die benötigt werden, um von der Startposition zur Endposition zu gelangen. In der zweiten Zeile sollen alle Befehle ausgegeben werden, die an den Roboter gesendet werden müssen. Gibt es mehrere mögliche Lösungen, kann das Programm eine beliebige davon ausgeben.
Ist es dem Roboter unmöglich, das Ziel zu erreichen, soll das Programm
Impossible ausgeben.Beispiele
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUTipp
Sie können den Startpunkt wie einen Boden (
.) behandeln und den Zielpunkt wie eine Wand (#).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB