c++ - 我正在尝试将迷宫遍历递归编码部分更改为 while 循环

Question

这是我的代码。

#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;
            }
        }
    }
}

我试图让我的 void mazeTraverse 函数成为一个 while 循环，而不是递归，但我被卡住了。

Answer 1

创建一个结构来保存 X、Y 和方向(这三项在调用之间发生变化)。我们称该结构为 State ;

创建一个 std::stack<State>目的。在更改它们之前将 X、Y 和方向的当前值压入堆栈，并在完成工作后弹出它们。

因此

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