用栈求解迷宫问题的所有路径及最短路径之5×5迷宫的代码c+

在使用栈解决迷宫问题时，我们通常会采用深度优先搜索（DFS）算法。对于找到所有路径，我们可以遍历每一个未访问过的节点，如果当前节点是出口，就将路径添加到结果集中；如果是墙壁，跳过；如果是已访问过的节点，也跳过以避免环路。以下是基于C++的一个简单示例，演示了如何使用栈来找出5x5迷宫的所有路径：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 模拟迷宫的二维数组，0代表空地，1代表墙，2代表起点，3代表终点
const int MAZE[5][5] = {
    {0, 0, 0, 0, 2},
    {0, 1, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 3, 0}
};

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 上下左右四个方向

bool visited[5][5]; // 记录每个位置是否已经访问过

void dfs(int x, int y, vector<vector<int>>& paths, int path_num) {
    if (x < 0 || y < 0 || x >= 5 || y >= 5 || MAZE[x][y] == 1 || visited[x][y]) return;
    visited[x][y] = true;
    
    paths[path_num].push_back(MAZE[x][y]); // 将当前位置添加到路径
    if (MAZE[x][y] == 3) {
        // 找到了出口，记录路径
        paths.push_back(paths[path_num]);
    } else {
        for (int i = 0; i < 4; ++i) {
            dfs(x + directions[i][0], y + directions[i][1], paths, path_num + 1); // 递归探索下一个方向
        }
    }
}

void findAllPaths(vector<vector<int>>& all_paths) {
    stack<pair<int, int>> s; // 使用堆栈保存待探索的位置
    s.push({0, 2}); // 起点
    visited[0][2] = true;
    
    while (!s.empty()) {
        int x = s.top().first, y = s.top().second;
        s.pop();
        
        if (MAZE[x][y] == 3) { // 遇到出口，开始记录路径
            dfs(x, y, all_paths, 0);
        } else {
            for (int i = 0; i < 4; ++i) {
                int newX = x + directions[i][0], newY = y + directions[i][1];
                if (!visited[newX][newY]) {
                    s.push({newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }
    }
}

int main() {
    vector<vector<int>> all_paths;
    findAllPaths(all_paths);

    cout << "All possible paths:" << endl;
    for (auto& path : all_paths) {
        for (int step : path) {
            cout << step << " ";
        }
        cout << endl;
    }

    return 0;
}

注意：这个代码仅展示了一个基本的迷宫寻找路径的例子，并不会处理最短路径问题。最短路径问题通常需要使用更复杂的数据结构如广度优先搜索（BFS），或者引入额外的信息，如路径长度信息。