使用表栈来解决迷宫问题使用c++写出其完整代码

表栈（Stack）常用于解决迷宫问题中的路径查找，特别是广度优先搜索（BFS）。这里是一个简单的C++代码示例，展示了如何用表栈实现二维数组形式的迷宫求解：

#include <vector>
#include <stack>

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

bool is_valid(int x, int y, const std::vector<std::vector<int>>& maze) {
    return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && !maze[x][y];
}

void solveMaze(std::vector<std::vector<int>>& maze, int& x, int& y, bool visited[]) {
    std::vector<int> stack;
    stack.push_back(x * maze[0].size() + y); // 把当前位置压入栈

    while (!stack.empty()) {
        int index = stack.top(); stack.pop();
        int gridIndex = index % maze[0].size(), row = index / maze[0].size();

        if (gridIndex == maze.size() - 1 && maze[row][gridIndex] == 1) {
            // 找到出口，打印路径
            while (row != y || gridIndex != x) {
                int nextRow = row, nextCol = gridIndex;
                for (int i = 0; i < 4; ++i) {
                    if (is_valid(nextRow + dy[i], nextCol + dx[i], maze) && !visited[nextRow + dy[i]][nextCol + dx[i]]) {
                        std::cout << "(" << nextCol << ", " << nextRow << ") -> ";
                        nextRow += dy[i]; nextCol += dx[i];
                    }
                }
                std::cout << "(" << x << ", " << y << ")";
                row = nextRow; gridIndex = nextCol;
            }

            break;
        }

        visited[row][gridIndex] = true;

        for (int i = 0; i < 4; ++i) {
            int newX = row + dy[i], newY = gridIndex + dx[i];
            if (is_valid(newX, newY, maze) && !visited[newX][newY]) {
                stack.push_back((newX * maze[0].size() + newY));
            }
        }
    }
}

int main() {
    // 初始化一个迷宫示例
    std::vector<std::vector<int>> maze = {
        {0, 0, 0, 1}, // 1 表示墙壁
        {0, 1, 0, 0},
        {0, 0, 0, 0},
        {1, 0, 0, 0} // 0 表示空地
    };

    int startX = 0, startY = 2; // 起始位置
    bool visited[maze.size()][maze[0].size()] = {false}; // 初始化所有位置为未访问

    solveMaze(maze, startX, startY, visited);

    return 0;
}

这个代码首先定义了四个方向的移动（dx 和 dy），然后通过栈来存储每个可能的下一步，并检查是否到达终点。找到出口后，它会回溯打印出从起点到终点的路径。