Python算法入门day7——栈和队列的应用(迷宫问题)_python 队列的应用迷宫问题

【题目描述】

给一个二维列表，表示迷宫(0表示通道，1表示围墙)。给出算法，求一条走出迷宫的路径。

一、栈——深度优先搜索

1.回溯法

2.思路：从一个节点开始，上下左右任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。

3.使用栈存储当前路径

4.使用匿名函数lambda定义坐标上下左右走，可以看看下面这篇

Python中lambda使用简单小结_alxe_made的博客-CSDN博客_lambda python用法lambda简单介绍1. 什么是lambda 简单来说，编程中提到的 lambda 表达式，通常是在需要一个函数，但是又不想费神去命名一个函数的场合下使用，也就是指匿名函数。这一用法跟所谓 λ 演算（题目说明里的维基链接）的关系，有点像原子弹和质能方程的关系，差别其实还是挺大的。举例子说明：g = lambda x : x+1g(1)输出：2可以这样...https://blog.csdn.net/alxe_made/article/details/80496690?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164820741516782184693638%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164820741516782184693638&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-80496690.142%5Ev5%5Epc_search_result_cache,143%5Ev6%5Econtrol&utm_term=python%E9%87%8Clambda%E6%80%8E%E4%B9%88%E7%94%A8&spm=1018.2226.3001.4187

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]
]#1代表围墙，0代表可以走的路
 
#匿名函数
dirs=[
    #x代表行，y代表列
    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 maze_path(x1,y1,x2,y2):#起点坐标(x1,y1),终点坐标(x2,y2)
    stack=[]
    test=1
    stack.append((x1,y1))
    while(len(stack)>0):#如果栈中没有元素，代表起点的上下左右都不通，推出循环
        curNode=stack[-1]#表示当前的坐标以及for循环以后的新坐标，因为栈是先进后出的，所以stack[-1]表示最后一个坐标
        
        if curNode[0]==x2 and curNode[1]==y2:#表示走到终点了
            for i in stack:
                print(i)
            return True
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])#下一个坐标，每个curNode都表示一个元组：0表示第x行，1表示第y列
            #判断下一跳是否为0，如果是0则将nextNode保存到栈，标记任意数，然后break，下一跳
            if maze[nextNode[0]][nextNode[1]]== 0:#等于0表示能走
                stack.append(nextNode)#有路则保存到栈中
                maze[nextNode[0]][nextNode[1]]=2#标记已经走过的路
                break #能找到一个就直接下一跳
        else:#回退
            
            maze[nextNode[0]][nextNode[1]]=2#走不通也代表走过，所以也要标记一下
            stack.pop()#回退
    #栈空
    else:
        print("没有路")
        return False
 
maze_path(1,1,8,8) 

【运行代码】

---

二、队列——广度优先搜索

1.找终点

【解题思路】

从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口。

使用队列存储当前正在考虑的节点。

可以用这张图来解释，扩起来的是用来存储当前的节点，一个节点进站，之前的父节点需要出列

假设x=13是终点，则下面延伸就是：(红色的代表队列里存储的数)

1 2 3 4 5 6 7

1 2 3 4 5 6 7 8 9 #6出队，将8，9元素加入队列中

1 2 3 4 5 6 7 8 9 10 #接着7出队，将10元素加入队列中

1 2 3 4 5 6 7 8 9 10 11#依次出队进队操作，直到终点加入到队中，结束

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12 13

 2.输出路径

【解题思路】

从终点开始倒着找起点，存储到列表中

出队序列： 1  2  3  4  5  6  7

哪点来的：-1  0  1  2  2  3  4 

假设7这个点是要找的终点，则返回原先来的那个点

所以7是由5过来的，所以跳转到下标2，然后5又是由3过来的，所以输出下标2，然后依次类推

输出下标 1，0，-1，得到路径。

---

【代码运算】

需要注意的是，要创建一个队列来存储移出队列的元素

from collections import deque #导入队列
#首先直接套用栈的迷宫和匿名函数
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]
]#1代表围墙，0代表可以走的路
 
#匿名函数
dirs=[
    #x代表行，y代表列
    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 print_r(path):
    #path里最后一个元素是终点
    curNode=path[-1]#终点
    realpath=[]#新列表
    #当第三个元素不是-1一直循环
    while curNode[2]!=-1:
        #如果不是-1，则把curNode放入新的列表里
        realpath.append((curNode[0],curNode[1]))
        #curNode[2]是由上一个点(len(path)-1)得来的
        #所以这样可以得到上一个点
        curNode=path[curNode[2]]
    #当等于-1时候，代表起点，将起点输出
    realpath.append((curNode[0],curNode[1]))
    realpath.reverse()#倒序
    for node in realpath:
        print(node)
def maze_path_queue(x1,y1,x2,y2):
    queue=deque()#创建一个队列
    queue.append((x1,y1,-1))#创建三维列表(起点坐标，下标)
    path=[] #用于存储被队列移除的数的下标
    while len(queue)>0:#队列为空的时候表示上下左右都走不通
        curNode=queue.popleft()#表示移出队列的第一个数
        path.append(curNode)
        if curNode[0]==x2 and curNode[1]==y2:
            #找到终点，输出所有路径
            print_r(path)
        for dir in dirs:
            nextNode = dir(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]]==0:
                queue.append((nextNode[0],nextNode[1],len(path)-1))
                maze[nextNode[0]][nextNode[1]]=2 #标记为已经走过的路
                #广义搜索不需要break
    #当队列为空时
    else:
        print("队列为空")
        return False
maze_path_queue(1,1,8,8)