用栈求解迷宫最短路径问题，使用C++

栈是一种先进后出（LIFO）的数据结构，非常适合用于解决迷宫问题中的最短路径搜索，特别是当路径需要回溯时。一种常见的算法是宽度优先搜索（Breadth-First Search, BFS），也可以通过广度优先的方式利用栈来实现。

以下是使用C++实现基本版的宽度优先搜索迷宫解决方案的步骤：

#include <vector>
#include <queue>
using namespace std;

// 定义迷宫的结构体（假设每个格子有0表示空地，1表示障碍）
struct Cell {
    bool visited;
    int distance; // 到起点的距离
};

class MazeSolver {
private:
    vector<vector<Cell>> maze;
    int start, end; // 起点和终点

public:
    MazeSolver(vector<vector<int>>& maze, int start, int end) : maze(maze), start(start), end(end) {}

    // 使用深度优先搜索，辅助函数
    void dfs(int x, int y, int dist) {
        if (x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1)
            return;

        maze[x][y].distance = dist;
        maze[x][y].visited = true;

        if (x == end) {
            cout << "Shortest path found: " << dist << endl;
            return;
        }

        // 邻居探索
        queue<pair<int, int>> neighbors;
        neighbors.push({x+1, y}); // 上
        neighbors.push({x-1, y}); // 下
        neighbors.push({x, y+1}); // 右
        neighbors.push({x, y-1}); // 左

        while (!neighbors.empty()) {
            auto [nx, ny] = neighbors.front();
            neighbors.pop();

            if (!maze[nx][ny].visited)
                dfs(nx, ny, dist + 1);
        }
    }

    // 主函数，开始搜索
    void bfs() {
        maze[start][start].distance = 0;
        maze[start][start].visited = true;
        queue<pair<int, int>> q;
        q.push({start, start});

        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();

            for (auto [dx, dy] : {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
                int nx = x + dx, ny = y + dy;
                if (isValid(nx, ny)) {
                    maze[nx][ny].distance = maze[x][y].distance + 1;
                    maze[nx][ny].visited = true;
                    q.push({nx, ny});
                }
            }
        }
    }

private:
    // 检查是否越界或者碰到墙壁
    bool isValid(int x, int y) {
        return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] != 1;
    }
};

int main() {
    // 初始化迷宫矩阵和起始点、结束点...
    vector<vector<int>> maze = ...;
    int start = ...;
    int end = ...;
    
    MazeSolver solver(maze, start, end);
    solver.bfs(); // 开始搜索
    return 0;
}