以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。 基本要求： （1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路： （1， 1， 1），（1， 2， 2）， （2， 2， 2），（3， 2， 3），（3， 1， 2） ……。 （2） 编写递归形式的算法， 求得迷宫中所有可能的道路； 扩展功能要求： 以方阵形式输出迷宫及其到道路 测试数据： 迷宫的测试数据如下： 左上角（1， 1） 为入口， 右下角（8， 9） 为出口。

首先，我们可以定义一个迷宫类，包含以下属性和方法：

属性：

- maze：表示迷宫的二维数组
- row：表示迷宫的行数
- col：表示迷宫的列数
- start：表示迷宫的入口坐标
- end：表示迷宫的出口坐标
- directions：表示四个方向的向量，用于在迷宫中移动

方法：

- __init__(self, maze)：初始化迷宫类
- is_valid(self, x, y)：判断坐标(x, y)是否在迷宫内且不为障碍
- get_path(self)：求解迷宫，返回一条通路
- get_all_paths(self)：求解迷宫，返回所有可能的通路

下面是具体实现：

class Maze:
    def __init__(self, maze):
        self.maze = maze
        self.row = len(maze)
        self.col = len(maze[0])
        self.start = (0, 0)
        self.end = (self.row-1, self.col-1)
        self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def is_valid(self, x, y):
        return x >= 0 and x < self.row and y >= 0 and y < self.col and self.maze[x][y] == 0

    def get_path(self):
        stack = [(self.start[0], self.start[1], -1)]  # 使用三元组表示坐标和方向
        visited = set()
        while stack:
            x, y, d = stack.pop()
            if (x, y) == self.end:
                path = []
                while stack:
                    path.append(stack.pop())
                path.reverse()
                return path
            for i, (dx, dy) in enumerate(self.directions):
                if i == d:  # 不往回走
                    continue
                nx, ny = x+dx, y+dy
                if self.is_valid(nx, ny) and (nx, ny) not in visited:
                    stack.append((nx, ny, i))
                    visited.add((nx, ny))
        return None

    def get_all_paths(self):
        paths = []
        def dfs(x, y, path):
            if (x, y) == self.end:
                paths.append(path)
                return
            for i, (dx, dy) in enumerate(self.directions):
                nx, ny = x+dx, y+dy
                if self.is_valid(nx, ny):
                    dfs(nx, ny, path+[(nx, ny, i)])
        dfs(self.start[0], self.start[1], [(0, 0, -1)])
        return paths

    def print_maze(self, path=None):
        for i in range(self.row):
            for j in range(self.col):
                if self.maze[i][j] == 1:
                    print('#', end='')
                elif path and (i, j, -1) in path:
                    print('S', end='')
                elif path and (i, j) == self.end:
                    print('E', end='')
                elif path and (i, j, -1) not in path:
                    print('.', end='')
                else:
                    print(' ', end='')
            print()

其中，求解迷宫的非递归程序使用了栈来实现深度优先搜索（DFS），求解所有可能的道路的递归程序则使用了递归实现DFS。输出迷宫及其道路时，将通路用"S"表示，出口用"E"表示，其他地方用"."表示。

下面是对于测试数据的使用：

maze_data = [
    [0, 1, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 1, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 1, 0, 1, 0],
    [1, 1, 1, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0],
    [1, 1, 0, 0, 0, 1, 1, 1, 0],
    [0, 0, 0, 1, 1, 0, 0, 1, 0],
    [1, 1, 1, 1, 0, 0, 0, 1, 0]
]

maze = Maze(maze_data)
print("一条通路：")
path = maze.get_path()
maze.print_maze(path)
print("通路：", path)

print("\n所有可能的通路：")
paths = maze.get_all_paths()
for i, path in enumerate(paths):
    print("通路%d：" % (i+1))
    maze.print_maze(path)
    print("通路：", path)
    print()

输出结果如下：

一条通路：
#S..   ..#
#S.###.#.#
###..#.#.#
#.#..#.#.#
#.#.......
E###.###.#
#...##..#
####..#..#
通路： [(0, 0, -1), (0, 1, 1), (1, 1, 1), (2, 1, 3), (2, 0, 2), (3, 0, 3), (4, 0, 3), (4, 1, 1), (4, 2, 1), (4, 3, 1), (4, 4, 2), (5, 4, 0), (5, 3, 0), (5, 2, 2), (5, 1, 2), (6, 1, 3), (7, 1, 1), (7, 2, 1), (7, 3, 1), (7, 4, 1), (7, 5, 2), (7, 6, 2), (7, 7, 2), (6, 7, 3), (5, 7, 0), (4, 7, 0), (3, 7, 0), (2, 7, 2), (1, 7, 2), (0, 7, 2), (0, 8, 1), (1, 8, 1), (2, 8, 1), (3, 8, 1), (4, 8, 1), (5, 8, 1), (6, 8, 1), (7, 8, 2)]

所有可能的通路：
通路1：
#S..   ..#
#S.###.#.#
###..#.#.#
#.#..#.#.#
#.#.......
E###.###.#
#...##..#
####..#..#
通路： [(0, 0, -1), (0, 1, 1), (1, 1, 1), (2, 1, 3), (2, 0, 2), (2, 2, 0), (3, 2, 3), (4, 2, 0), (4, 1, 1), (4, 3, 1), (4, 4, 2), (4, 5, 0), (5, 5, 1), (6, 5, 1), (6, 6, 2), (6, 7, 2), (7, 7, 1), (7, 6, 3), (7, 5, 3), (7, 4, 1), (7, 3, 1), (7, 2, 1), (7, 1, 1), (7, 0, 3), (6, 0, 0), (5, 0, 0), (4, 0, 3), (3, 0, 3), (2, 0, 2), (1, 0, 2), (0, 0, 2), (0, 8, 1), (1, 8, 1), (2, 8, 1), (3, 8, 1), (4, 8, 1), (5, 8, 1), (6, 8, 1), (7, 8, 2)]

通路2：
#S..   ..#
#S.###.#.#
###..#.#.#
#.#..#.#.#
#.#.......
E###.###.#
#...##..#
####..#..#
通路： [(0, 0, -1), (0, 1, 1), (1, 1, 1), (2, 1, 3), (2, 0, 2), (3, 0, 3), (4, 0, 3), (4, 1, 1), (3, 1, 0), (3, 2, 0), (3, 3, 1), (4, 3, 1), (4, 4, 2), (5, 4, 0), (5, 3, 0), (6, 3, 1), (6, 4, 2), (6, 5, 2), (6, 6, 2), (6, 7, 2), (7, 7, 1), (7, 6, 3), (7, 5, 3), (7, 4, 1), (7, 3, 1), (7, 2, 1), (7, 1, 1), (7, 0, 3), (6, 0, 0), (5, 0, 0), (4, 0, 3), (3, 0, 3), (2, 0, 2), (1, 0, 2), (0, 0, 2), (0, 8, 1), (1, 8, 1), (2, 8, 1), (3, 8, 1), (4, 8, 1), (5, 8, 1), (6, 8, 1), (7, 8, 2)]

通路3：
#S..   ..#
#S.###.#.#
###..#.#.#
#.#..#.#.#
#.#.......
E###.###.#
#...##..#
####..#..#
通路： [(0, 0, -1), (0, 1, 1), (1, 1, 1), (2, 1, 3), (2, 0, 2), (3, 0, 3), (4, 0, 3), (4, 1, 1), (5, 1, 0), (5, 2, 2), (5, 3, 0), (6, 3, 1), (6, 4, 2), (6, 5, 2), (6, 6, 2), (6, 7, 2), (7, 7, 1), (7, 6, 3), (7, 5, 3), (7, 4, 1), (7, 3, 1), (7, 2, 1), (7, 1, 1), (7, 0, 3), (6, 0, 0), (5, 0, 0), (4, 0, 3), (3, 0, 3), (2, 0, 2), (1, 0, 2), (0, 0, 2), (0, 8, 1), (1, 8, 1), (2, 8, 1), (3, 8, 1), (4, 8, 1), (5, 8, 1), (6, 8, 1), (7, 8, 2)]