bfs 蓝桥杯 走迷宫 python

给定一个N×M 的网格迷宫 G。

G 的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 00表示）。

已知迷宫的入口位置为 (x1,y1)，出口位置为 (x2​,y2​)。

问从入口走到出口，最少要走多少个格子。

输入描述

输入第 11 行包含两个正整数 N,M，分别表示迷宫的大小。

接下来输入一个 MN×M 的矩阵。

若 Gi,j​=1 表示其为道路，否则表示其为障碍物。

最后一行输入四个整数 x1​,y1​,x2​,y2​，表示入口的位置和出口的位置。

输出描述

输出仅一行，包含一个整数表示答案。

若无法从入口到出口，则输出 -1。

输入输出样例

示例 1

输入

5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5 

输出

8

代码 

from queue import Queue
n,m=map(int,input().split())
vis=[[0 for i in range(m)] for j in range(n)]
lb=[]
dir=[[1,0],[-1,0],[0,1],[0,-1]]
def right(x,y):#是否在范围内，判断是否出界
    if x >= 0 and x < n and y >= 0 and y < m :
        return True
    return False
for i in range(n):
    s=input().split()
    lb.append(s)
x,y,a,b=map(int,input().split())#(x,y)入口(a,b)出口
x=x-1
y=y-1
a=a-1
b=b-1
s=""
def bfs(x,y):
    global s
    q=Queue()
    q.put((x,y,0))
    vis[x][y]=1
    while q.empty() == False:
        now = q.get()#now为三元素元组x,y,step
        if now[0] ==a and now[1] == b:
            s=now[2]
            return 1
        for i in range(4):
            x1 = now[0] + dir[i][0]
            y1 = now[1] + dir[i][1]
            if right(x1,y1)and lb[x1][y1] == "1" and vis[x1][y1] == 0:
                step = now[2] + 1
                q.put((x1, y1, step))
                vis[x1][y1] = 1
if bfs(x,y)==1:
    print(s)
else:
    print(-1)

​