Ich versuche, meine Maze Traversal rekursive Codierung Teil in eine while-Schleife ändern

Question

Hier ist mein Code.

#include <iostream>
using namespace std;

enum Direction { EAST, NORTH, WEST, SOUTH };
const int size = 12;
int xStart = 2; int yStart = 0;

char *maze2[ ] = {
    "############",
    "#...#......#",
    "..#.#.####.#",
    "###.#....#.#",
    "#....###.#..",
    "####.#.#.#.#",
    "#..#.#.#.#.#",
    "##.#.#.#.#.#",
    "#........#.#",
    "######.###.#",
    "#......#...#",
    "############",
};
void printMaze ( char maze[][ size ] );
void mazeTraverse( char maze[][ size ], int x, int y, int direction );

int main()
{
    char maze[ size ][ size ];
    for (int x = 0; x < size; x++ )
        for (int y = 0; y < size; y++)
            maze[ x ][ y ] = maze2[ x ][ y ];
    printMaze( maze );
    mazeTraverse( maze, xStart, yStart, EAST);
}

void printMaze ( char maze[][ size ] )
{
    for ( int x = 0; x < size; x++)
    {
        for ( int y = 0; y < size; y++)
            cout << maze[ x ][ y ];
        cout << endl;
    }
    cout << endl;
    cout << "\nHit return to see next move\n";
    cin.get();
}
bool validMove( char maze[][ size ], int x, int y )
{
    return x >= 0 && x < size && y >= 0 && y < size && maze[x][y] != '#';
}

bool coordsAreEdge( int x, int y )
{
    return x== 0 || x== size - 1 || y == 0 || y== size - 1;
}

void mazeTraverse( char maze[][ size ], int x, int y, int direction )
{
    maze[ x ][ y ] = 'x';
    printMaze( maze );
    if (coordsAreEdge(x, y) && (x != xStart || y!= yStart ))
    {
        cout <<"\nMaze successfully exited!\n\n";
        return;
    }else{
        for ( int move = direction, count = 0; count < 4;
            count++, move++, move %=4 )
        {
            int nextX; int nextY;
            switch ( move )
            {
            case SOUTH: nextX = x + 1; nextY = y; break;
            case EAST: nextX = x; nextY = y + 1; break;
            case NORTH: nextX = x - 1; nextY = y; break;
            case WEST: nextX = x; nextY = y - 1; break;
            default: ;
            }
            if (validMove( maze, nextX, nextY ))
            {
                //Recursion move part 1
                //mazeTraverse ( maze,  nextX ,  nextY, (move + 3)%4 );

                return;
            }
        }
    }
}

Ich versuche, meine ungültige mazeTraverse Funktion eine while-Schleife, anstelle der Rekursion zu machen und ich bin stecken.

Answer 1

Erstellen Sie eine Struktur, die X, Y und Richtung enthält (die drei Dinge, die sich zwischen Aufrufen ändern). Wir nennen diese Struktur State ;

Erstellen einer std::stack<State> Objekt. Schieben Sie die aktuellen Werte für X, Y und Richtung auf den Stapel, bevor Sie sie ändern, und löschen Sie sie, nachdem Sie Ihre Arbeit erledigt haben.

daher

 while(.....)
 {
      push state
      Do work of mazeTraverse 
      pop state
 }

Answer 2

Es wäre schön gewesen, wenn du beschrieben hättest, wie das Traversal funktioniert. Wenn ich den Code nicht falsch lese, bewegen Sie sich im Grunde nach Süden/Osten/Norden/Westen an jeder Position, die kein # enthält und innerhalb der Grenzen der Matrix liegt.

Sie können dies iterativ mit Hilfe einer BF-Suche tun: http://en.wikipedia.org/wiki/Breadth-first_search oder, angewandt auf eine Matrix, der Lee-Algorithmus: http://en.wikipedia.org/wiki/Lee_algorithm die mit Hilfe einer FIFO-Warteschlange effizient implementiert werden kann, was ich hier beschreibe: FloodFill-Algorithmus ändern, um Voronoi-Territorium für zwei Datenpunkte zu erhalten?

Ihre validMove-Funktion bleibt gleich: Sie fügen der Warteschlange nur dann eine Position hinzu, wenn diese gültig ist. Im Grunde genommen bleiben alle Überprüfungen gleich, nur dass Sie eine FIFO-Warteschlange anstelle eines impliziten Stapels verwenden, um Ihre Zustände zu speichern.

Answer 3

Sie könnten stattdessen eine Breadth-First-Suche mit einer Standard queue y while Schleife.

typedef pair<int, int> Point;

queue<Point> path;

Point start(xStart, yStart);
path.push(start);

const int move_x[] = {-1, 0, 1, 0};
const int move_y[] = {0, -1, 0, 1};

while (!path.empty())
{
  Point p = path.front();
  int x = p.first, y = p.second;
  maze[x][y] = 'x';

  path.pop();

  if (coordsAreEdge(x,y) && p != start)
  {
    // Finished
    break;
  }

  for (int i = 0; i < 4; ++i)
  {
    int newx = x + move_x[i];
    int newy = y + move_y[i];

    if (validMove(maze, newx, newy))
      path.push(Point(newx, newy));
  }
}

Das sollte genügen. Beachten Sie jedoch, dass es nicht getestet ist.

Sie können die Leistung verbessern, indem Sie stattdessen A* verwenden, aber das ist ein wenig komplizierter. Lassen Sie es mich wissen, wenn Sie den kürzesten Weg auch mit diesem Code finden müssen.

EDIT: Beachten Sie, dass, wenn Sie die queue zu einer stack (und ändern path.front() まで path.top() ), dann erhalten Sie stattdessen eine Tiefensuche (DFS), was Ihr Code auch tut. Die DFS findet jedoch nicht den kürzesten Pfad (falls dies überhaupt notwendig ist).