c++求解非递归迷宫问题

以下是一个用C++解决非递归迷宫问题的示例代码：

#include <iostream>
#include <stack>
using namespace std;

// 定义迷宫的大小
const int ROW = 5;
const int COL = 5;

// 定义迷宫
int maze[ROW][COL] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}
};

// 定义迷宫坐标结构
struct Point {
    int x;
    int y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};

// 非递归求解迷宫
bool solveMaze() {
    stack<Point> path; // 使用栈记录路径
    Point start(0, 0); // 起点坐标
    Point end(ROW - 1, COL - 1); // 终点坐标

    // 判断起点和终点是否为障碍物
    if (maze[start.x][start.y] == 1 || maze[end.x][end.y] == 1)
        return false;

    path.push(start); // 将起点入栈

    while (!path.empty()) {
        Point current = path.top();
        path.pop();

        // 判断是否到达终点
        if (current.x == end.x && current.y == end.y) {
            cout << "找到迷宫的出口!" << endl;
            return true;
        }

        // 标记当前位置为已访问
        maze[current.x][current.y] = 1;

        // 检查当前位置的四个相邻位置
        // 上方
        if (current.x - 1 >= 0 && maze[current.x - 1][current.y] == 0) {
            path.push(Point(current.x - 1, current.y));
        }
        // 下方
        if (current.x + 1 < ROW && maze[current.x + 1][current.y] == 0) {
            path.push(Point(current.x + 1, current.y));
        }
        // 左方
        if (current.y - 1 >= 0 && maze[current.x][current.y - 1] == 0) {
            path.push(Point(current.x, current.y - 1));
        }
        // 右方
        if (current.y + 1 < COL && maze[current.x][current.y + 1] == 0) {
            path.push(Point(current.x, current.y + 1));
        }
    }

    cout << "迷宫无解!" << endl;
    return false;
}

int main() {
    if (solveMaze()) {
        cout << "路径如下：" << endl;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                cout << maze[i][j] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

以上代码通过使用栈实现了非递归方式解决迷宫问题。迷宫使用二维数组表示，其中0表示可通过的路径，1表示障碍物。程序从起点开始，每次选择一个未访问的相邻位置，并将其入栈，直到到达终点或栈为空。如果找到了路径，则输出路径，并将迷宫中的路径位置标记为1；如果找不到路径，则输出"迷宫无解"。