python 走迷宫问题
题目描述】给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
【输入格式】
第一行包含两个整数 n 和 m。
接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
【输出格式】
输出一个整数，表示从左上角移动至右下角的最少移动次数。
【数据范围】
1≤n,m≤100
【输入样例】
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
8
【解题思路】
BFS的典中典。from collections import *
n,m = map(int,input().split())
mp = [*(m+5)]
for i in range(n):
mp.append(+list(map(int,input().split())))
dir = [(1,0),(-1,0),(0,1),(0,-1)]
st = [*(m+5) for _ in range(n+5)]
def bfs():
q = deque()
q.append()
st=1
while q:
tx,ty,step = q.popleft()
if tx==n and ty==m:
print(step)
return
for x_,y_ in dir:
nx,ny = tx+x_,ty+y_
if nx<1 or nx>n or ny<1 or ny>m:continue
if mp==1 or st:continue
q.append( )
st=1
bfs()
页:
[1]