bfs 蓝桥杯走迷宫 python

134 阅读 0 评论 89 点赞

我是靠谱客的博主负责翅膀，这篇文章主要介绍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

输入

复制代码

输出

复制代码

1
8

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)