用栈求解迷宫问题的最短路径代码

以下是使用栈来求解迷宫问题的最短路径的代码实现（假设迷宫是由 0 和 1 组成的二维数组，其中 0 表示通路，1 表示障碍）：

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

const int MAXSIZE = 100;

struct Pos {
    int x, y;
};

int maze[MAXSIZE][MAXSIZE];  // 迷宫
int visited[MAXSIZE][MAXSIZE];  // 记录是否访问过
int m, n;  // 迷宫的行数和列数
stack<Pos> s;  // 存储路径的栈

// 判断一个位置是否可以访问
bool isAccessible(int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n)  // 越界
        return false;
    if (maze[x][y] == 1 || visited[x][y] == 1)  // 障碍或已访问过
        return false;
    return true;
}

// 求解迷宫问题的最短路径
void solveMaze(int startX, int startY, int endX, int endY) {
    s.push({startX, startY});  // 将起点入栈
    visited[startX][startY] = 1;  // 标记起点已访问过

    while (!s.empty()) {
        Pos currPos = s.top();
        s.pop();

        // 如果到达终点，输出路径并退出
        if (currPos.x == endX && currPos.y == endY) {
            cout << "Shortest path: ";
            while (!s.empty()) {
                Pos p = s.top();
                cout << "(" << p.x << "," << p.y << ") ";
                s.pop();
            }
            cout << "(" << endX << "," << endY << ")" << endl;
            return;
        }

        // 将当前位置的相邻可访问位置入栈
        if (isAccessible(currPos.x, currPos.y-1)) {  // 左
            s.push({currPos.x, currPos.y-1});
            visited[currPos.x][currPos.y-1] = 1;
        }
        if (isAccessible(currPos.x, currPos.y+1)) {  // 右
            s.push({currPos.x, currPos.y+1});
            visited[currPos.x][currPos.y+1] = 1;
        }
        if (isAccessible(currPos.x-1, currPos.y)) {  // 上
            s.push({currPos.x-1, currPos.y});
            visited[currPos.x-1][currPos.y] = 1;
        }
        if (isAccessible(currPos.x+1, currPos.y)) {  // 下
            s.push({currPos.x+1, currPos.y});
            visited[currPos.x+1][currPos.y] = 1;
        }
    }

    // 没有找到路径
    cout << "No path found!" << endl;
}

int main() {
    // 读入迷宫
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
            visited[i][j] = 0;
        }
    }

    // 求解迷宫问题的最短路径
    solveMaze(0, 0, m-1, n-1);

    return 0;
}

该代码使用了深度优先搜索来遍历迷宫，并使用栈来存储路径，并在到达终点时输出路径。