用python深度优先遍历解迷宫问题

267次阅读

共计 2285 个字符，预计需要花费 6 分钟才能阅读完成。

导读	这篇文章主要给大家介绍了关于 python 迷宫问题深度优先遍历的相关资料, 深度优先搜索算法 (Depth-First-Search), 是搜索算法的一种, 需要的朋友可以参考下

一、迷宫介绍

用 python 解迷宫问题，迷宫是一个二维列表，本次用深度优先解开迷宫问题。定义起点和终点，从一个位置到下一个位置只能通过向上或下或左或右，走一步来实现，从起点出发，如何找到一条到达终点的通路。

二、深度优先遍历

简单那我们的案例来讲就是，随便选择一条路，一直走，走不动了，再回头重新选择新的路

# 1 为墙，0 为路
maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

首先我们先设置一个起点和终点

start = (1, 1)
end = (8, 8)

判断当前这个点，0 就是路可以走，1 为墙不能走

对于一个点的下一个点的坐标准说明：

上走：r – 1, c
下走：r + 1, c
左走：r, c – 1
右走：r, c + 1

那我们这个迷宫的某个一个点达到了不能走的地步了，就是死胡同了，它就得原路返回

这时我们就有一个概念，就是栈，栈的思想就是：先进后出

怎么理解呢，可以举一个小例子，就是食堂阿姨，每天早上蒸包子，他是一层一层放蒸笼
那放到最后，学生来吃包子，她是从上往往外拿，最上面就是最后放的，最下面是最先放的，所以就叫做先进后出

其实 list 就是一个栈，比如我们放一个空列表，然后我们用这个列表直接 append

再用 pop 进行取出，就会取到 append 的最后一个元素

# 定义列表，列表里面放的就是每一步走的坐标，[r, c]
# 第一步就是起始位置，也就是 start
list01 = [start]

走过的路定义为 2

row, col = now
# python 里的解构也叫解包 now 包括两个位置，一个行，一个列
maze[row][col] = 2
# 这个代表就是走过的点，为 2，因为你走过的路是不能再走的，除了走不通返回的时候，也是为了走不通按原来走过的路原路返回

核心代码：

if maze[row - 1][col] == 0:
    # 上方可以走
    list01.append((row - 1, col))
    continue
elif maze[row][col + 1] == 0:
    # 右方可以走
    list01.append((row, col + 1))
    continue
elif maze[row + 1][col] == 0:
    # 下方可以走
    list01.append((row + 1, col))
    continue
elif maze[row][col - 1] == 0:
    # 左方可以走
    list01.append((row, col - 1))
    continue

最终代码，可以运行一下试试：

maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
 start = (1, 1)
end = (8, 8) # 定义列表，列表里面放的就是每一步走的坐标，[r, c]
# 第一步就是起始位置，也就是 start
list01 = [start] 
# 定义循环，让它走
# 列表里最后存的就是下一步走的地方，当前列表有东西才能继续走
while list01:
    # 当前走到的节点是哪一个节点，也就是最后走的一步，是哪一步，去列表的最后的一个值就是索引 -1
    now = list01[-1]
    if now == end:  # 如果现在的 now 等于我们之前定义的终点 end
        print(list01)
        print("出来了")
        break
    row, col = now
    # python 里的解构也叫解包 now 包括两个位置，一个行，一个列
    maze[row][col] = 2
    # 这个代表就是走过的点，为 2，因为你走过的路是不能再走的，除了走不通返回的时候，也就是为了走不通按原来走过的路原路返回
 
    # continue 结束本次循环，从新开始判断走路
    if maze[row - 1][col] == 0:
        # 上方可以走
        list01.append((row - 1, col))
        continue
    elif maze[row][col + 1] == 0:
        # 右方可以走
        list01.append((row, col + 1))
        continue
    elif maze[row + 1][col] == 0:
        # 下方可以走
        list01.append((row + 1, col))
        continue
    elif maze[row][col - 1] == 0:
        # 左方可以走
        list01.append((row, col - 1))
        continue
    else: # 走不通过，直接循环干掉每一步，重新调整路线
        list01.pop()
 
else:
    print("这个迷宫走不通")

总结

到此这篇关于 python 迷宫问题深度优先遍历的文章就介绍到这了。