蓝桥杯 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$，表示入口的位置和出口的位置。

$1\le N,M\le 10^2，0\le G_{i,j}\le 1,1\le x_1,x_2\le N,1\le y_1,y_2\le M$。

输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口到出口，则输出 -1−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

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

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

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)

最后

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

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