广度优先搜索BFS

迷宫题：

给定一个二维矩阵，1表示不能走，0表示能走。再给定一个起点和终点，只可以上下左右，求出最短路径。

广度优先搜索依次搜索走1步、走2步、走3步能到的位置，走的路径逐渐增大，到终点时立即返回，所以最终当函数返回时一定是最短路径。

from collections import deque

dirs = [(-1,0),(1,0),(0,-1),(0,1)] #上下左右
arrows = ['^','v','<','>']

class Node:
    def __init__(self, x, y, deep, path):
        self.x = x
        self.y = y
        self.deep = deep    #保存到达当前点走了多少步
        self.path = path    #表示到达当前点的路径，即走法

def BFS(mat,start,end):
    M = len(mat)
    N = len(mat[0])
    visited = [[False for j in range(N)] for i in range(M)]  #表示每个点是否已经走过
    visited[start.x][start.y] = True   #将起点处置为走过

    que = deque([start])  #用队列保存要处理的点
    while(que):
        now = que.popleft()  #每次处理队首
        if now.x == end.x and now.y == end.y:  #到达终点，循环结束
            print(now.path)
            return now.deep
        for i,dir in enumerate(dirs):  #尝试往四个方向走
            next = Node(now.x+dir[0],now.y+dir[1],now.deep+1,now.path+[arrows[i]])  #选定一个方向，算出该点，深度加一，路径加一
            if next.x < 0 or next.x >= M or next.y < 0 or next.y >= N or mat[next.x][next.y]==1:  #出范围或不能走时continue
                continue
            if not visited[next.x][next.y]:  #该方向未访问过
                visited[next.x][next.y]=True  #标记为访问
                que.append(next)  #将该点入队，等待后续向这条路径继续前进
    return -1



mat = [[0,1,0,0,1],
       [1,0,0,1,1],
       [0,0,1,1,0],
       [1,0,0,0,1]]
start = Node(0,0,0,[])
end = Node(1,1,0,[])
print(BFS(mat,start,end))