python数据结构与算法--队列广度优先搜索算法

经典的数据结构算法题:走迷宫

[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,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,1,1]

把上述二维矩阵看成一个迷宫，0是可以走的路，1是墙不可以走，只允许上、下、左、右四个方向走，每次走1步,现要求从(1,1)这个坐标点开始到(8,8)坐标点，求出最短的路径。注意–数组（1，1）为第2行第2列，（8，8）为第9行第9列.

分析

引入队列的概念，队列是先进先出的顺序，具体概念可以百度，下面根据题目分析算法：
1.定义二维数组，导入迷宫

maze=[
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,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,1,1]
]  #maze座位迷宫的数组名字

2.引入匿名函数组成的’不同前进同方向‘列表

dirs=[
    lambda x,y:(x+1,y), #向下
    lambda x,y:(x-1,y), #向上
    lambda x,y:(x,y-1), #向左
    lambda x,y:(x,y+1)  #向右
]

其中(x,y)是每一步的坐标点

3.程序部分

from collection import deque
def maze_path_queue(x1,y1,x2,y2):          #写入(x1,y1)为起点坐标，(x2,y2)为终点坐标
    queue=deque()					 	   #实例化python给我们封装好的队列	
    queue.append((x1,y1,-1))               #起点坐标进队列，-1表明了这是起点，它的上一级不存在，所以给了标志为-1
    path=[]                                #路径数组，用来记录迷宫的路径
    while len(queue)>0:                    #判断条件，队列只要不为空，就一直进行下去，因为只要不为空，说明还没有到终点，继续前进
        curNode=queue.popleft()            #curNode当前坐标位置，queue.popleft()从前端出队列，给到curNode的容器中
        path.append(curNode)               #路径列表添加相应的路径
        if curNode[0]==x2 and curNode[1]==y2:# 因为curNode是元组形式(x,y)，如果curNode坐标已经到终点了
            #终点
            print_r(path)					#执行print_r(path),另外写了函数
            return True                     
        for dir in dirs:                    #for 循环遍历dirs的方法列表
            nextNode=dir(curNode[0],curNode[1])# 生成下一个坐标点，
            if maze[nextNode[0]][nextNode[1]]==0: #如果下一个坐标点为0，即该坐标点可以走，那说明这条路是通的，至少没有撞墙
                queue.append((nextNode[0],nextNode[1],len(path)-1))#后续节点进队，len(path)-1是因为nextNode是由curNode生成出来，
               													    #每一个CurNode[2]都对应着它们各自上一节点的位置索引，
                													#上一个curNode被添加到了path列表的最后一个位置，
                													#因此nextNode[2]也就是curNode所在path列表的位置索引，
                													#即为len(path)-1
                maze[nextNode[0]][nextNode[1]]=2 #将走过的低方标记为2，不走回头路
    else:
        print('没有路')
        return False

def print_r(path):			#只有已经走完了才会运行到这个函数
    curNode=path[-1]  		#因此path的最后一个元素就是终点，把终点坐标给到curNode

    realpath=[]            #再定义一个空的列表，用来存放最短的路径，
   							 #因为之前的path是将所有走过的路径(包括走了一部分没到终点的)都存放在里面了，我只需要最短路径

    while curNode[2] != -1: #进入循环，从最后开始往前寻找走过的路，最开始我们给起点设置了curNode[2]=-1,
   										 #因此这个循环就是只要当前点不是起点，就依次从后往前一个点一个点去找
        realpath.append(curNode[0:2]) #将从后往前的找到的坐标点赋值给realpath(真实路径用作保存)
        curNode=path[curNode[2]]      # 既然是一个循环，依次从后往前找的过程就是不断更新curNode的过程，
      								  #curNode就通过在path列表中寻找curNode[2]这个索引的坐标值

    realpath.append(curNode[0:2])    #结束循环，需要把起点放进去
    realpath.reverse()                #因为是从后往前找的,realpath中的点坐标是从终点开始一直到起点，
    								#因此需要来一个反向，这样的话就是正向输出了
    for node in realpath:			#使用一个循环进行输出
        print(node)

输出

(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)

进程已结束,退出代码0