我正在尝试将我的迷宫遍历递归编码部分更改为 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 对象。在更改 X、Y、方向的当前值之前将其压入堆栈，在完成工作后将其弹出。

因此

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

Answer 2

如果您能描述一下遍历的工作原理，那就太好了。如果我没有读错代码，那么您基本上是在不包含 # 且在矩阵范围内的任何位置上向南/东/北/西移动。

您可以使用 BF 搜索迭代地执行此操作： http://en.wikipedia.org/wiki /Breadth-first_search 或者，应用于矩阵，Lee 算法：http://en .wikipedia.org/wiki/Lee_algorithm 可以使用 FIFO 队列有效地实现，我在这里描述了如何操作：更改 FloodFill-Algorithm 以获取两个数据点的 Voronoi Territory？

您的 validMove 函数将保持不变：您仅当该位置有效时才将其添加到队列中。基本上所有检查都保持不变，只是您使用 FIFO 队列而不是隐式堆栈来保存状态。

Answer 3

您可以使用广度优先搜索，而不是使用标准的 queue 和 while 循环。

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

那应该可以解决问题。请注意，它尚未经过测试。

您可以通过使用 A* 来提高其性能，但这有点复杂。如果您还需要从此代码中找到最短路径，请告诉我。

编辑：请注意，如果将 queue 更改为 stack （并将 path.front() 更改为 path.top()），然后您将得到深度优先搜索（DFS），这就是您的代码所做的。然而，DFS 找不到最短路径（如果有必要的话）。