一、题目描述
给定一个 n*m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中0表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于 start 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从 start 移动至 end 处，至少需要移动多少次。
数据保证 start 处和 end 处的数字为0，且至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤1001≤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 队列）
- 起始点坐标加入队列，设置距离为
0 while队列不为空，队头出队一个节点，如果这个节点的上／下／左／右可以到达（不碰壁、不超过边界，之前未被访问），则把能到达的加入队列，距离+1- 如果到达终点，返回距离
题目要求最短路径，为什么代码中没有 m i n min min 的体现呢？
答：因为广度优先搜索其实已经有寻找到最短路径的功能了，可以理解为总部同时派出多路兵马并行搜索（各路兵马在分岔口又再分出多路并进），并且总部发出命令时，每一路兵马都只前进一步，那么哪一路兵马先到达目的地，则该路线肯定是最近的。
""" 【迷宫问题】 0 为通路 1 为障碍 """
def minSteps(mat, start, end):
# visited初始化
n = len(mat)
m = len(mat[0])
vis = [[False for j in range(m)] for i in range(n)]
vis[start[0]][start[1]] = True
queue = []
# 加入的是这个节点的元组表示 [x，y，距离]
queue.append([start[0],start[1], 0])
# 四个方向
dx=[-1,0,1,0]
dy=[0,-1,0,1]
while queue:
x, y, c = queue.pop(0)
# 出口，到达终点
if x == end[0] and y == end[1]:
return c
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0 <= nx < n and 0 <= ny < m and mat[nx][ny] == 0 and vis[nx][ny]==False:
queue.append([nx, ny, c + 1])
vis[nx][ny] = True
if __name__ == '__main__':
# mat = [[0,0,0,0,0,1],
# [0,1,1,0,1,0],
# [0,1,0,0,1,0],
# [0,0,1,0,0,0],
# [0,1,0,0,1,0],
# [0,0,0,1,0,1]]
mat = [[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]]
start = [0, 0]
end = [1, 3]
ans = minSteps(mat, start, end)
print(ans)
京公网安备 11010502036488号