【问题描述】以一个 m×n 的长方阵表示迷宫0 和1分别表示迷宫中的通路和障碍。设计一个程序对任意设定的迷宫求出一条从入口到出口的通路或得出没有通路的结论。要求实现以下功能：1以链表作存储结构的栈类型编写一个求解迷宫的非递归程序。求得的通路以 ij 的形式按通路顺序输出其中ij 为迷宫中的一个坐标。2求得迷宫中所有可能的通路并输出最短路径。【作业要求】需要提交代码及实验报告。源代码关键部分须包含详

算法思想：

1. 首先将迷宫的起点入栈，并标记为已访问。
2. 如果栈不为空，则取出栈顶元素，判断是否为终点，如果是则得到一条通路，将通路存储起来。
3. 如果栈顶元素不是终点，则将其周围的未访问的通路入栈，并标记为已访问。
4. 重复步骤2和步骤3，直到找到一条通路或者栈为空。

求解迷宫的非递归程序代码如下：

class StackNode:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def is_empty(self):
        return self.top is None

    def push(self, x, y):
        node = StackNode(x, y)
        if self.is_empty():
            self.top = node
        else:
            node.next = self.top
            self.top = node

    def pop(self):
        if self.is_empty():
            return None
        else:
            node = self.top
            self.top = self.top.next
            return node.x, node.y

def find_path(maze):
    if maze is None or len(maze) == 0 or len(maze[0]) == 0:
        return None

    m = len(maze)
    n = len(maze[0])
    visited = [[False] * n for _ in range(m)]
    stack = Stack()
    stack.push(0, 0)
    visited[0][0] = True
    paths = []

    while not stack.is_empty():
        x, y = stack.pop()
        if x == m-1 and y == n-1:
            paths.append((x, y))
            break

        paths.append((x, y))
        if x+1 < m and maze[x+1][y] == 0 and not visited[x+1][y]:
            stack.push(x+1, y)
            visited[x+1][y] = True
        elif y+1 < n and maze[x][y+1] == 0 and not visited[x][y+1]:
            stack.push(x, y+1)
            visited[x][y+1] = True
        elif x-1 >= 0 and maze[x-1][y] == 0 and not visited[x-1][y]:
            stack.push(x-1, y)
            visited[x-1][y] = True
        elif y-1 >= 0 and maze[x][y-1] == 0 and not visited[x][y-1]:
            stack.push(x, y-1)
            visited[x][y-1] = True
        else:
            paths.pop()

    return paths

maze = [
    [0, 1, 1, 1, 1],
    [0, 0, 0, 1, 1],
    [1, 1, 0, 0, 1],
    [1, 1, 1, 0, 1],
    [1, 1, 1, 0, 0]
]

paths = find_path(maze)
if paths is not None and len(paths) > 0:
    print("迷宫中存在通路：")
    for path in paths:
        print(path)
else:
    print("迷宫中不存在通路")

迷宫中是否有通路以及求得迷宫中所有可能的通路，可以通过判断最终得到的路径列表是否为空来确定。

输出迷宫通路最短路径，可以通过比较所有可能的通路的长度，选择最短的路径作为最短路径。在上述代码的基础上做一些修改，即可实现这一功能