Maze Solving Graph mit

Question

Hey, ich war in einem lokalen Programmierwettbewerb und sie hat mich gebeten, diese Frage, die ich nicht so helfen Sie mir auf diesem bitte könnte.

Schreiben Sie ein Programm, dass Lasten aus einer Datei die Größe eines Labyrinths und dann das Labyrinth selbst. Um das Labyrinth zu modellieren wir das Zeichen „S“, der angibt, die Startzelle verwenden „“ freie Zelle, die angibt, „#“ ist eine Wand, und „F“ ist die letzte Zelle. Schreiben Sie ein Programm, das einen Weg von der Startzelle in die letzte Zelle finden. Sie können in dem Labyrinth denken, dass es ein Roboter ist, dass Befehle gehorchen, so für die folgende Labyrinth sollte der Roboter die folgenden Befehle angezeigt: oben, oben, rechts, rechts, unten, unten.

Labyrinth 1 Textdatei

5 5
#####
#...#
#.#.#
#S#T#
#####

Labyrinth 2 Textdatei

4 5
#.#.#
#.#.#
#S#T#
#####

Schreiben Sie Ihr Programm im Allgemeinen (das Labyrinth Eingang maximal höchstens 200x200 sein kann).

Hilfe wäre sehr geschätzt. Ich bin nur ein steigender sophmore so, wenn Sie mir den Code dann zur Verfügung stellen könnte ich es verstehen konnte, und sie tun es wieder bymyself.

Answer 1

Eine Möglichkeit, einen Weg zu finden:

1. eine Warteschlange von Zellen hat zu überprüfen, und eine Anzahl von Schritten für jede Zelle von dort zum Ziel.
2. Stellen Sie die Endung Zelle wieder auf 0, und fügen Sie sie in die Warteschlange.
3. Während die Warteschlange nicht leer ist:
   1. Holen Sie sich eine Zelle aus der Warteschlange.
   2. Für jede freie Nachbarzelle, zu vergleichen, die gräflichen aktuelle Zelle + 1 zu der gräflichen Nachbarzelle. Wenn es weniger ist, der, wenn die Nachbarzelle nicht eine Zählung noch nicht haben, die Nachbarzelle des Grafen auf die aktuellen Zelle des Grafen + 1 gesetzt, dann die Nachbarzelle in die Warteschlange.

Wenn die Warteschlange leer ist, jede freie Zelle im Labyrinth (das vom Ziel erreicht werden kann) wird die Anzahl der Schritte in dem kürzesten Weg zum Ziel hat. Wenn eine Zelle nicht eine Zählung hat, gibt es keinen Weg aus es zum Ziel.

Wenn die Startzelle hat eine Zählung,

1. Holen Sie sich das Grafenstartzelle.
2. werden jede Nachbarzelle überprüfen Sie für eine Anzahl von (count - 1). Es wird sein, und das ist der nächste Schritt auf dem Weg. Nehmen Sie die Richtung zu dieser Zelle, und dann diese Zelle bekommen, und wenn es nicht das Ziel, wiederholen Sie Schritt 2 mit dieser Zelle.

Ich werde es Ihnen überlassen, um herauszufinden, wie das Labyrinth zu laden. Das ist der einfache Teil von all dem.

Answer 2

Falls Sie nicht wissen, was zu suchen: http://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm und diese enthält viel mehr Informationen: http://www.astrolog.org/labyrnth/algrithm.htm

Answer 3

Der Code ist zu viel hier zu schreiben, aber die gängigste Methode, Labyrinthe zu lösen, ist in eine Richtung auf den Weg, und an jedem rechts abbiegen können Sie nach rechts machen.

Dies ist auf Arbeit garantiert, solange die Start- und Ausgang sind in einer der vier umgebenden Wände. Für Labyrinthe, die, es ist eine Übung in der Rekursion nicht ihre Start- und Ausfahrt an den Wänden haben.

Sehen Sie, was Sie können sich mit Code-weise basierend aus, dass als Ausgangspunkt!

HTH, James