Kürzester Pfad auf einem Gitter
Angenommen, Sie haben ein Labyrinth in Form eines Gitters mit
r Zeilen und c Spalten. Ihre Aufgabe ist es, die Länge des kürzesten Weges von der Startzelle bis zur Zielzelle zu ermitteln.Das Labyrinth ist folgendermaßen aufgebaut:
- Der Boden ist ein Punkt (
.).
- Mauern sind Rauten (
#).
- Der Startpunkt ist der Großbuchstabe
S.
- Die Zielzelle ist der Großbuchstabe
E.
Sie können sich zwischen zwei benachbarten Zellen (links, rechts, oben oder unten) bewegen, sofern es sich nicht um Mauern handelt.
Gesucht ist die Länge des kürzesten Weges zwischen der Startzelle und der Zielzelle.
Input
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
r und c (1 ≤ r, c ≤ 1000).Die nächsten
r Zeilen beinhalten c Zeichen, die das Gitter beschreiben. Jede Zelle ist entweder ein Boden (.), eine Mauer (#), ein Startpunkt (S) oder ein Zielpunkt (E). Es ist garantiert, dass genau ein S und genau ein E vorhanden sind.Output
Das Programm soll die Länge des kürzesten Pfads von
S nach E ausgeben. Falls es keinen Pfad von S zu E gibt, soll das Programm Impossible ausgeben.Examples
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Tip
Es ist nicht immer nötig, explizit einen Graphen zu erstellen, um einen BFS-Algorithmus auszuführen. Manchmal kann man implizite Graphen wie Gitterstrukturen verwenden und darauf direkt einen BFS anwenden.
Hint
Sie können das Gitter als Graph behandeln und ein zweidimensionales Array
d[][] verwenden, das den kürzesten Abstand von der Startzelle bis zur jeweiligen aktuellen Zelle speichert.Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB