python迷宫问题深度优先遍历实例

一、迷宫介绍

用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迷宫问题深度优先遍历的文章就介绍到这了,更多相关python迷宫深度优先内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径

    深度优先算法(DFS 算法)是什么? 寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径.主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点.如果走到某个节点发现无路可走,那么就会回退到上一个节点,重新选择其他路径.直到找到出口,或者退到起点再也无路可走,游戏结束.当然,深度优先算法,只要查找到一条行得通的路径,就会停止搜索:也就是说只要有路可走,深度优先算法就不会回退到上一步. 如果你依然在编程的世界里迷茫,可以加入我们的Python学

  • Python深度优先算法生成迷宫

    本文实例为大家分享了Python深度优先算法生成迷宫,供大家参考,具体内容如下 import random #warning: x and y confusing sx = 10 sy = 10 dfs = [[0 for col in range(sx)] for row in range(sy)] maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] #1:up 2:down 3:left 4:right opera

  • python迷宫问题深度优先遍历实例

    一.迷宫介绍 用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

  • C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

    本文实例讲述了C++实现图的邻接矩阵存储和广度.深度优先遍历的方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 1 0 2 1 0 3 1 2 3 1 2 4 1 1 4 1 输入结束(此行不必输入) 注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a

  • python实现树的深度优先遍历与广度优先遍历详解

    本文实例讲述了python实现树的深度优先遍历与广度优先遍历.分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个节点 广度优先 顺序:A - B - C - D - E - F - G - H - I 代码实现 def breadth_travel(self, root): """利用队列实现树的层次遍历""" if root == None: r

  • Python迷宫生成和迷宫破解算法实例

    迷宫生成 1.随机PRIM 思路:先让迷宫中全都是墙,不断从列表(最初只含有一个启始单元格)中选取一个单元格标记为通路,将其周围(上下左右)未访问过的单元格放入列表并标记为已访问,再随机选取该单元格与周围通路单元格(若有的话)之间的一面墙打通.重复以上步骤直到列表为空,迷宫生成完毕.这种方式生成的迷宫难度高,岔口多. 效果: 代码: import random import numpy as np from matplotlib import pyplot as plt def build_tw

  • java图的深度优先遍历实现随机生成迷宫

    最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢. 1.从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问. 2.对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • Python利用openpyxl库遍历Sheet的实例

    方法一,利用 sheet.iter_rows() 获取 Sheet1 表中的所有行,然后遍历 import openpyxl wb = openpyxl.load_workbook('example.xlsx') sheet = wb.get_sheet_by_name('Sheet1') for row in sheet.iter_rows(): for cell in row: print(cell.coordinate, cell.value) print('--- END OF ROW

  • Python二叉树定义与遍历方法实例分析

    本文实例讲述了Python二叉树定义与遍历方法.分享给大家供大家参考,具体如下: 二叉树基本概述: 二叉树是有限个元素的几个,如果为空则为空二叉树,或者有一个结点称之为根节点,分列根节点两侧的为二叉树的左右子节点,二叉树有如下的性质: 1. 二叉树的每个结点不存在度大于2的结点 2. 二叉树的第i层至多有2^{i-1}个结点 3. 深度为k的二叉树至多有2^k - 1个结点 4. 二叉树中,度为0的结点数N0比度为2的结点数N2大1,即存在N2 + 1 = N0 Python代码: #codin

  • python图的深度优先和广度优先算法实例分析

    本文实例讲述了python图的深度优先和广度优先算法.分享给大家供大家参考,具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回溯到v,

随机推荐