以一个 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）非递归求解迷宫通路的程序：

首先，我们需要定义一个以链表为存储结构的栈类型。每个栈节点包含三个数据域：i，j和d，分别表示在迷宫中的坐标和前进的方向。

class MazeStackNode:
    def __init__(self, i, j, d):
        self.i = i
        self.j = j
        self.d = d
        self.next = None

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

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

    def push(self, i, j, d):
        node = MazeStackNode(i, j, d)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.isEmpty():
            return None
        node = self.top
        self.top = node.next
        return node

接下来，我们编写一个非递归算法来求解迷宫通路。该算法使用一个栈来保存当前的位置和前进方向，同时使用一个 visited 数组来记录已经访问过的位置。算法流程如下：

1. 将起点 (i0, j0) 和前进方向 d0 入栈，并将 visited[i0][j0] 设置为 True。
2. 从栈中弹出当前位置和前进方向，将其记为 (i, j, d)。
3. 如果当前位置是终点 (i1, j1)，则输出路径并结束。
4. 否则，按照前进方向 d 依次尝试前进，直到找到一个未访问过的位置 (i2, j2)。
5. 如果找到了未访问过的位置 (i2, j2)，则将其入栈，并将 visited[i2][j2] 设置为 True。
6. 如果没找到未访问过的位置，则将当前位置出栈。
7. 重复步骤 2 到步骤 6，直到栈为空，此时无法到达终点，输出无解信息。

下面是完整的 Python 代码实现：

def solve_maze(maze, i0, j0, i1, j1):
    m, n = len(maze), len(maze[0])
    visited = [[False] * n for _ in range(m)]
    stack = MazeStack()
    stack.push(i0, j0, 0)

    while not stack.isEmpty():
        i, j, d = stack.pop()
        visited[i][j] = True

        if i == i1 and j == j1:
            print_path(stack)
            return

        for nd in range(d+1, 5):
            if nd == 1 and i > 0 and not visited[i-1][j] and maze[i-1][j] == 0:
                stack.push(i-1, j, nd)
                break
            elif nd == 2 and j < n-1 and not visited[i][j+1] and maze[i][j+1] == 0:
                stack.push(i, j+1, nd)
                break
            elif nd == 3 and i < m-1 and not visited[i+1][j] and maze[i+1][j] == 0:
                stack.push(i+1, j, nd)
                break
            elif nd == 4 and j > 0 and not visited[i][j-1] and maze[i][j-1] == 0:
                stack.push(i, j-1, nd)
                break
        else:
            continue

    print("No solution.")

def print_path(stack):
    if stack.isEmpty():
        return
    node = stack.pop()
    print_path(stack)
    print("({}, {}, {})".format(node.i, node.j, node.d))

该算法的时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。

（2）递归求解迷宫通路的程序：

首先，我们需要定义一个递归函数来求解迷宫通路。该函数需要接受当前位置和前进方向作为参数，并返回是否能够到达终点。为了记录路径，我们还需要定义一个栈类型，每个栈节点包含三个数据域：i，j和d，分别表示在迷宫中的坐标和前进的方向。

class MazeStackNode:
    def __init__(self, i, j, d):
        self.i = i
        self.j = j
        self.d = d
        self.next = None

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

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

    def push(self, i, j, d):
        node = MazeStackNode(i, j, d)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.isEmpty():
            return None
        node = self.top
        self.top = node.next
        return node

接下来，我们编写一个递归函数 solve_maze_recursive，该函数使用回溯的方法来求解迷宫通路。函数流程如下：

1. 如果当前位置是终点 (i1, j1)，则返回 True。
2. 按照前进方向 d 依次尝试前进，如果能够到达一个未访问过的位置 (i2, j2)，则将其入栈，并递归调用 solve_maze_recursive(i2, j2, nd)。
3. 如果递归调用返回 True，则说明已找到通路，将当前位置入栈并返回 True。
4. 如果前进方向已经尝试完毕，则将当前位置出栈并返回 False。

下面是完整的 Python 代码实现：

def solve_maze_recursive(maze, i, j, i1, j1, d, stack):
    if i == i1 and j == j1:
        return True

    for nd in range(d+1, 5):
        if nd == 1 and i > 0 and maze[i-1][j] == 0 and (i-1, j) not in stack:
            stack.push(i-1, j, nd)
            if solve_maze_recursive(maze, i-1, j, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()
        elif nd == 2 and j < len(maze[0])-1 and maze[i][j+1] == 0 and (i, j+1) not in stack:
            stack.push(i, j+1, nd)
            if solve_maze_recursive(maze, i, j+1, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()
        elif nd == 3 and i < len(maze)-1 and maze[i+1][j] == 0 and (i+1, j) not in stack:
            stack.push(i+1, j, nd)
            if solve_maze_recursive(maze, i+1, j, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()
        elif nd == 4 and j > 0 and maze[i][j-1] == 0 and (i, j-1) not in stack:
            stack.push(i, j-1, nd)
            if solve_maze_recursive(maze, i, j-1, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()

    return False

该算法的时间复杂度为指数级别，空间复杂度为 $O(mn)$，因此只适合求解小规模的迷宫。