【问题描述】以一个 m×n 的长方阵表示迷宫0 和1分别表示迷宫中的通路和障碍。利用C++设计一个程序：对任意设定的迷宫求出一条从入口到出口的通路或得出没有通路的结论。要求实现以下功能：1以链表作存储结构的栈类型编写一个求解迷宫的非递归程序。求得的通路以 ij 的形式按通路顺序输出其中ij 为迷宫中的一个坐标。、2求得迷宫中所有可能的通路并输出最短路径。

以下是一个用C++实现的求解迷宫的非递归程序：

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

// 定义迷宫的行列数
const int m = 5;
const int n = 5;

// 定义迷宫的通路和障碍
const int maze[m][n] = {
    {1, 0, 1, 1, 1},
    {1, 0, 1, 0, 1},
    {1, 1, 1, 1, 1},
    {1, 0, 0, 0, 1},
    {1, 1, 1, 0, 1}
};

// 定义坐标结构体
struct Point {
    int x;
    int y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

// 判断坐标是否合法
bool isValid(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 1;
}

// 求解迷宫的非递归函数
void solveMaze() {
    stack<Point> s;  // 使用栈存储通路
    vector<vector<bool>> visited(m, vector<bool>(n, false));  // 记录访问过的坐标
    vector<vector<Point>> prev(m, vector<Point>(n, Point(-1, -1)));  // 记录每个坐标的前一个坐标

    // 入口坐标
    Point start(0, 0);
    // 出口坐标
    Point end(m-1, n-1);

    // 将入口加入栈中
    s.push(start);
    visited[start.x][start.y] = true;

    while (!s.empty()) {
        Point current = s.top();
        s.pop();

        // 如果到达出口，停止搜索
        if (current.x == end.x && current.y == end.y) {
            break;
        }

        // 上下左右四个方向的坐标偏移
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        // 搜索上下左右四个方向
        for (int i = 0; i < 4; i++) {
            int nextX = current.x + dx[i];
            int nextY = current.y + dy[i];

            // 如果坐标合法且未被访问过
            if (isValid(nextX, nextY) && !visited[nextX][nextY]) {
                s.push(Point(nextX, nextY));
                visited[nextX][nextY] = true;
                prev[nextX][nextY] = current;
            }
        }
    }

    // 判断是否找到通路
    if (!visited[end.x][end.y]) {
        cout << "迷宫中没有通路" << endl;
    } else {
        // 输出通路坐标
        vector<Point> path;
        Point current = end;
        while (current.x != -1 && current.y != -1) {
            path.push_back(current);
            current = prev[current.x][current.y];
        }
        cout << "迷宫的通路为：" << endl;
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << "(" << path[i].x << ", " << path[i].y << ")" << endl;
        }
    }
}

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

这个程序使用了一个栈来存储通路，使用了一个二维数组来记录坐标是否被访问过，使用了另一个二维数组来记录每个坐标的前一个坐标。通过搜索上下左右四个方向来寻找通路，直到找到出口或者栈为空。最后根据前一个坐标数组来输出通路。

对于迷宫中所有可能的通路，并输出最短路径，可以采用广度优先搜索的方法。在上面的代码中，可以将栈改为队列，并将搜索顺序改为广度优先搜索的顺序，最后输出的通路即为最短路径