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)
​

最后

以上就是负责翅膀为你收集整理的bfs 蓝桥杯 走迷宫 python的全部内容，希望文章能够帮你解决bfs 蓝桥杯 走迷宫 python所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。