Python之迷宫问题的DFS和BFS_bfs 迷宫问题求解 python

1.问题描述：

给定一个二维列表由零一组成，一代表墙，零代表路，给定起始坐标给终点坐标，若能走出迷宫求出路径坐标。

2.深度优先（DFS）

深度优先即一条路走到黑，走到走不通了就回退，“回退”那我们就想到了用栈来实现，起始点先入栈，然后看上下左右哪个位置能走，但我们如何表示方向呢？可以用lamda表达式组成的列表

该列表接收当前坐标，输出下一个可能的坐标，遍历一遍如果nextnode上的值等于0，就将其入栈，并将走过地方的值设为2,如果发现四周等走不了，就将该位置出栈，回溯到栈顶即上一个元素，看能否往其他地方走，还是不行，再pop，再到上一个元素，以此类推

Talk is cheap,show me the code!

maze=[
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1],
          [1,0,0,0,1,1,0,0,0,1,0,0,0,1],
          [1,0,1,0,0,0,0,1,0,1,0,1,0,1],
          [1,0,1,0,1,1,1,1,0,1,0,1,0,1],
          [1,0,1,0,0,0,0,0,0,1,1,1,0,1],
          [1,0,1,1,1,1,1,1,1,1,0,0,0,1],
          [1,0,1,0,0,0,0,0,0,0,0,1,0,1],
          [1,0,0,0,1,1,1,0,1,0,1,1,0,1],
          [1,0,1,0,1,0,1,0,1,0,1,0,0,1],
          [1,0,1,0,1,0,1,0,1,1,1,1,0,1],
          [1,0,1,0,0,0,1,0,0,1,0,0,0,1],
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
 
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)
]
 
def maze_path(x1,y1,x2,y2):
    stack=[]
    stack.append((x1,y1))
    while(len(stack)>0):
        curNode=stack[-1]
        if curNode[0]==x2 and curNode[1]==y2:
            #到终点了
            for p in stack:
                print(p)
            return True
        #x,y四个方向x-1，y；x+1，y;so on
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[-1])
            #如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]]==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,2,1)

3.广度优先

相比较下，广度优先实现就要更难一些，相当于是从起点开始几个方向同时进行，同时入队，如果走（用一次）完就出队，最后用一个列表来记录路径

maze=[
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1],
          [1,0,0,0,1,1,0,0,0,1,0,0,0,1],
          [1,0,1,0,0,0,0,1,0,1,0,1,0,1],
          [1,0,1,0,1,1,1,1,0,1,0,1,0,1],
          [1,0,1,0,0,0,0,0,0,1,1,1,0,1],
          [1,0,1,1,1,1,1,1,1,1,0,0,0,1],
          [1,0,1,0,0,0,0,0,0,0,0,1,0,1],
          [1,0,0,0,1,1,1,0,1,0,1,1,0,1],
          [1,0,1,0,1,0,1,0,1,0,1,0,0,1],
          [1,0,1,0,1,0,1,0,1,1,1,1,0,1],
          [1,0,1,0,0,0,1,0,0,1,0,0,0,1],
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

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)
]
from collections import deque

def print_r(path):
    curNode=path[-1]
    realpath=[]
    while curNode[2]!=-1:
        realpath.append((curNode[0:2]))
        curNode=path[curNode[2]]
    realpath.append(curNode[0:2])#放起点
    realpath.reverse()
    print(realpath)
    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)
            return True
        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

    else:
        print("寄")
        return False

maze_path_queue(1,1,5,1)

不多说，代码胜过所有语言