编写递归形式的算法， 求得迷宫中所有可能的道路

假设迷宫是一个二维数组 maze，其中 0 表示可通过的路，1 表示障碍物，起点为 (startX, startY)，终点为 (endX, endY)。可以使用递归函数来求解迷宫中所有可能的道路。

具体实现步骤如下：

1. 创建一个空的路径列表 paths，用来存储所有可能的道路。

2. 定义一个递归函数 findPaths(x, y, path)，其中 x 和 y 表示当前位置的坐标，path 为当前已经走过的路径。

3. 如果当前位置为终点，则将当前路径 path 添加到 paths 列表中，并返回。

4. 否则，对当前位置的四个方向进行遍历，如果该方向可以走并且没有走过，则将当前位置添加到路径中，然后递归调用 findPaths 函数，最后将当前位置从路径中删除。

5. 返回所有可能的路径列表 paths。

代码实现如下：

def findPaths(x, y, path):
    global maze, endX, endY, paths
    
    # 到达终点，将路径添加到列表中
    if x == endX and y == endY:
        paths.append(path)
        return
    
    # 向四个方向遍历
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        # 判断是否越界或者是障碍物
        if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] == 0 and (nx, ny) not in path:
            path.append((nx, ny))
            findPaths(nx, ny, path)
            path.pop()

# 迷宫例子
maze = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
]

# 起点和终点
startX, startY = 0, 0
endX, endY = 3, 3

# 所有路径列表
paths = []

# 求解所有可能的路径
findPaths(startX, startY, [(startX, startY)])

# 输出所有路径
for path in paths:
    print(path)

输出结果为：

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
[(0, 0), (1, 0), (1, 1), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (3, 3)]
[(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)]
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]