Die Aufnahme einer Labyrinth-Pfad-Lösung mit einem Stapel

Ich bin zu generieren, die eine Lösung für ein Labyrinth mit einer linked-list-Implementierung eines Stacks in gewisser Weise. Das Labyrinth ist Lesen in einem .txt-Datei und enthält 0 ist für Freiflächen und 1 für Wände. Die Aufnahme einer Labyrinth-Pfad-Lösung mit einem Stapel
<- Ziemlich sicher, dass ein exit muss in der unteren Zeile? Diese drei 0?

Den Algorithmus, den ich bin versucht zu verwenden ist:

While Not At End
    If Can Go North
        Go North
    ElseIf Can Go East
        Go East
    ElseIf Can Go South
        Go South
    ElseIf Can Go West 
        Go West
    EndIf
Wend

Den Weg habe ich schon versucht es beruhte auf den ++ - Operationen ausführen innerhalb einer array-index. Ich war nicht bewusst, das array-subskript-operator [ nahm Vorrang vor + + so jetzt muss ich überdenken umgehen. Bevor Sie dies tun, möchte ich sichergehen, dass diese Methode auch die Arbeit in den ersten Platz. Könnte jemand einen Blick auf meinen algo-code so weit und einige feed zurück? (Anmerkung: ich muss noch hinzufügen, in einigen code zu verfolgen, Wege zu vermeiden, irgendeine Art von Endlosschleife)

bool notSolved = true;
        int path = 0;
        row = 0;
        col = 0;

        rowStack.push(row);
        colStack.push(col);

        while (notSolved){

        //(from perspective of person looking at maze on screen)
        if (maze[row--][col] == 0){//if you can go up, go up
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row][col++] == 0){//else if you can go right, go right
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row++][col] == 0){//else if you can go down, go down
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row][col--] == 0){//else if you can go left, go left
        rowStack.push(row);
        colStack.push(col);
        path++;
        }

            if((maze[row][col] == 0) && (row == (size - 1))){//if we reached an exit
                cout << "Solution Path:" << endl;
                for (int i = 0; i < path; i++){
                    cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
                    rowStack.pop();
                    colStack.pop();
                }
            notSolved = false;
            }
        }

Problem mit dem ausführen von [ vor ++:
Die Aufnahme einer Labyrinth-Pfad-Lösung mit einem Stapel

Jede Hilfe dankbar, vielen Dank!

  • Rekursion ist dein Freund auf diese ein.
  • Sie haben eine spezielle Frage?
  • Ich glaube nicht, dass Algorithmus ist besonders gut, zum Beispiel, wenn Sie laufen in der rechten Wand, während er in einer horizontalen tunnel, Sie hüpfen hin und her, von rechts nach Links für immer.
  • Suche zuerst der Breite besser funktioniert, auf Labyrinthe, so dass in diesem Fall eine Warteschlange könnte ein besserer "Freund" als Rekursion. Auch wenn Sie sich entscheiden, zu gehen, Tiefe-zuerst, könnten Sie besser dran mit einem stack und einer "while" - Schleife statt der Rekursion. Da der Suchraum wächst als N^2, die Gefahr, dass die Stapel in einen rekursiven Aufruf ganz real wird.
InformationsquelleAutor darko | 2011-11-30
  1. 2

    Dein Algorithmus funktioniert nicht in einigen Labyrinthe, die kreisförmigen Pfade: wenn man einmal in einem dieser, werden Sie sich im Kreis zu drehen. Um dies zu beheben, benötigen Sie ein boolean-array besucht[R][C][DIR], wobei DIR eine Zahl von null bis drei vertreten eine Richtung. Beim verlassen der Zelle [r][c] in Richtung [d], setzen Sie besuchte[r][c][d] auf true. Das nächste mal Sie besuchen die gleiche Zelle, sehen Sie, wenn Sie es verlassen in die gleiche Richtung vor; wenn Sie getan haben, überspringen Sie die Richtung, und gehen Sie zum nächsten auf der ganzen Linie.

    • Hmm, ich glaube, ich habe, besuchte array arbeiten, aber ich habe Probleme. Gibt es einen besseren Weg, es zu implementieren, in dem, wenn Aussagen Hier ist das problem:imgur.com/5rstN, geht rechts, runter, rechts, rechts, trifft die Wand dreht sich dann um und bleibt stecken. Hier ist mein neuer code:pastebin.com/uhp9MKfc
    • Der code für die überprüfung, ob Sie schon an einer Stelle sieht gut aus, jetzt müssen Sie implementieren, backtracking, ein ausgefallener name für "was ist zu tun, wenn Sie stecken bleiben". In Ihrem Fall, Sie brauchen, um pop-der Letzte Schritt von Ihrem rowStack/colStack, gehen Sie zurück zu der vorherigen Zelle und weiter in die nächste Richtung, in die Sie vorher noch nicht probiert haben.
    • hmm, Mein Erster Gedanke ist das hinzufügen von ein anderes Ende: else{//if stuck rowStack.pop(); colStack.pop(); row = rowStack.top(); col = colStack.top(); } Aber alles, was jetzt zu tun scheint, ist pop-jeder vorherigen Schritt Weg von der Oberseite des Stapels, bis es leer ist
    • Sie müssen sich an die Spitze vor dem Aufruf von pop. Sie müssen auch überprüfen, ob der stack leer ist, bevor Sie es knallen. Schließlich müssen Sie schließen Sie den ifs in einer Schleife, denn wenn Sie zurückweichen, Sie müssen weiter in die nächste Richtung, die Sie noch nicht versucht haben.
    • Was brauche ich, um zu betrachten, vor dem Aufruf von pop? Was ich bin versucht zu tun, ist es pop den Stapel und dann neu zuweisen, row und col zu den vorherigen Räumen Wert, so dass Sie gehen und versuchen welche Richtung auch immer, es hat nicht versucht, noch. Meine if-Anweisungen sind eingeschlossen in eine Schleife: Wnotsolved: pastebin.com/VSE2qBDu
    • Sie müssen neu anordnen Anrufe von pop und top, so wie hier: else{ row = rowStack.top(); col = colStack.top(); rowStack.pop(); colStack.pop(); }
    • lassen Sie uns weiter, diese Diskussion im chat
    • chat ging?

    InformationsquelleAutor dasblinkenlight
  2. 0

    ++ und -- tatsächlich ändern Sie die row /col-Variablen. Ich denke, Sie wollen zu tun maze[row - 1][col] == 0 und dann, nachdem Sie verschoben haben, aktualisieren Sie die Zeile position.

    InformationsquelleAutor Andy Ray
Schreibe einen Kommentar