数据结构之用栈解迷宫问题

给定一个二维列表，表示迷宫的轮廓（0表示通道，1表示墙），用栈结构完成算法，求一条走出迷宫的路径。 

实现思路：回溯法，从一个点开始，任意找一个能走的点，当找到不能走的点时，退回上一个点寻找是否有其他方向的点。 

代码示例

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

# 定义方向匿名函数
dirs = [
    lambda x, y: (x + 1, y),  # 右
    lambda x, y: (x, y + 1),  # 下
    lambda x, y: (x - 1, y),  # 左
    lambda x, y: (x, y - 1),  # 上
]

def search_path(x1, y1, x2, y2):
    # 用列表模拟栈结构，只用append和pop操作
    stack = []
    # 压入起始位置
    stack.append((x1, y1))
    # 栈空表示没有路
    while len(stack) > 0:
        # 取当前位置
        cur_x, cur_y = stack[-1]
        # 已经到达终点时停止
        if cur_x == x2 and cur_y == y2:
            return stack
        # 四个方向尝试
        for dir in dirs:
            # 获取下一个点
            next_x, next_y = dir(cur_x, cur_y)
            # 保证不出界
            if 0 <= next_x < len(maze[0]) and 0 <= next_y < len(maze):
                # 0表示能走通
                if maze[next_y][next_x] == 0:
                    # 往能走通的方向走一步
                    stack.append((next_x, next_y))
                    # 记录已经走过，防止重复
                    maze[next_y][next_x] = 2
                    break
        else:  # 四个方向都走不通，死路，回退
            stack.pop()
            # 设置已经尝试过了，走不通
            maze[cur_y][cur_x] = 3
    else:
        return None

path = search_path(0, 0, 9, 9)
print(path)