给定一个二维列表,表示迷宫的轮廓(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)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/305