蓝桥杯 python 走迷宫 BFS

148 阅读 0 评论 98 点赞

我是靠谱客的博主能干面包，这篇文章主要介绍蓝桥杯 python 走迷宫 BFS，现在分享给大家，希望可以做个参考。

蓝桥杯 python 走迷宫 BFS

题目描述
给定一个 N $\times$ M 的网格迷宫 G。GG的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 0 表示）。

已知迷宫的入口位置为 ( $x_1$ , $y_1$ )，出口位置为 ( $x_2$ , $y_2$ )。问从入口走到出口，最少要走多少个格子。

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

接下来输入一个 N $\times$ M 的矩阵。若 $G_{i,j}$ =1 表示其为道路，否则表示其为障碍物。

最后一行输入四个整数 $x_1$ , $y_1$ , $x_2$ , $y_2$ ，表示入口的位置和出口的位置。

$N,Mleq10^2，0leq G_{i,j}leq 1, 1leq x_1,x_2leq N, 1leq y_1, y_2leq M$ 。

输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口到出口，则输出 -1−1。
输入输出样例
示例 1
输入

复制代码

输出

复制代码

1
2
8

解题思路
用队列
但是我不能理解用vis = [[0] * m ] * n 生成一个二维矩阵来保存距离答案是错误的，只能vis = [[0 for i in range(m)] for j in range(n)] 动态生成。有理解的在评论区里说一声。

vis = [[0] * m ] * n 表示
列表*n，所有列表共享地址，这样的话vis矩阵永远改的是第一个。

复制代码

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 collections import deque
n, m = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
vis = [[0 for i in range(m)] for j in range(n)] # 动态生成
# vis = [[0] * m ] * n # vis不能这样生成
x1, y1 , x2, y2 = map(int,input().split())
q = deque()
def bfs(x,y):
q.append([x,y])
# 标记为非0 表示访问过
并且作为累加步数
后面要减一
vis[x][y] =1
while q:
# 当队列不空
now = q.popleft()
# 出队
nx = now[0] # now_x
ny = now[1] # now_y
if nx == x2-1 and ny == y2-1: # 到终点
break
for i in d:
# 向4个方向搜索
dx = nx+i[0]
dy = ny+i[1]
if 0 <= dx < n and 0 <= dy < m:
# 0 未访问过
并且不是障碍物
if vis[dx][dy] == 0 and g[dx][dy] == 1:
q.append([dx,dy])
# 入队
# 累加 之前的点加上1
非0 表示访问过
vis[dx][dy] = vis[nx][ny] + 1
return vis[x2-1][y2-1]
# 后面要减一
因为起始点为1累加的
print(bfs(x1-1,y1-1)-1)