用c++实现：用栈实现简单迷宫问题求解

在C++中，我们可以利用栈的数据结构来解决简单的迷宫问题，也就是寻找从起点到终点的路径。这里我们通常会采用广度优先搜索（BFS，Breath-First Search）算法，因为迷宫问题本质上是一个二维网格，而栈正好支持“先进先出”（FIFO）的特点。

下面是一个简单的迷宫问题的C++实现步骤：

1. 定义迷宫矩阵：一个二维数组表示每个单元格是墙、空地还是已经访问过的标记。

2. 定义一个`bool`类型的标志`visited`，用于记录当前单元格是否已经被访问过。

3. 定义一个`Stack<int>`用于存储要探索的节点（x坐标和y坐标），首先将起点入栈。

4. 使用一个循环，当栈不为空时：
- 弹出栈顶元素，即当前节点(x, y)。
- 如果这个位置是终点或者可以通行（不是墙且未访问过），则找到了一条路径，返回结果。
- 否则，检查该节点的上下左右邻居，如果邻居是空地且未访问过，将其标记为已访问并入栈。

5. 若遍历完所有路径仍未找到，说明无解，返回空或false。

以下是伪代码示例：

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

// 检查当前位置是否可行
bool is_valid(int x, int y, const vector<vector<bool>>& maze) {
    return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && !maze[x][y];
}

// 主函数，解决迷宫问题
bool solve_maze(int start_x, int start_y, int end_x, int end_y, vector<vector<bool>>& maze) {
    stack<pair<int, int>> path;
    vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false));
    path.push({start_x, start_y});
    visited[start_x][start_y] = true;

    while (!path.empty()) {
        int x = path.top().first;
        int y = path.top().second;
        path.pop();

        if (x == end_x && y == end_y) {
            return true; // 找到了路径
        }

        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (is_valid(x + dx, y + dy, maze) && !visited[x + dx][y + dy]) {
                    visited[x + dx][y + dy] = true;
                    path.push({x + dx, y + dy});
                }
            }
        }
    }

    return false; // 无解
}

// 示例迷宫和入口出口
void test() {
    vector<vector<bool>> maze = {...};
    int start_x = ...;
    int start_y = ...;
    int end_x = ...;
    int end_y = ...;

    bool result = solve_maze(start_x, start_y, end_x, end_y, maze);
    cout << (result ? "找到了路径" : "无解") << endl;
}

int main() {
    test();
    return 0;
}