bfs迷宫最短路径-Python

解题思路: bfs 建议看b站这个视频

https://www.bilibili.com/video/BV1CM4y1o7nZ/?spm_id_from=333.880.my_history.page.click&vd_source=b93da48f51cf32a81aabe9bda3bf5a2c

注意事项:

参考代码:

t = int(input())
while t:
   n, m = map(int, input().split())
   arr = []
   for _ in range(n):
       a = list(i for i in str(input()))
       arr.append(a)

   arr_0 = [[0] * m for _ in range(n)]

   queue = []  # queue记录每个点的位置i，j和第n步
   for i in range(n):
       for j in range(m):
           if arr[i][j] == "S":
               arr_0[i][j] = 1
               queue.append([i, j, 0])  # 先把起点[i,j,0]记录进queue，起点看作走了0步
           if arr[i][j] == "E":
               e1, e2 = i, j  # 终点的坐标[e1, e2]

   dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

   while len(queue): # 重点是这个while循环，搞清楚这一块就可以啦
       x, y = queue[0][0], queue[0][1]
       # print(queue)
       if x == e1 and y == e2:
           print(queue[0][-1])  # 打印走到终点的步数
           break

       for i in range(4):
           nx, ny = x + dir[i][0], y + dir[i][1]
           if 0 <= nx < n and 0 <= ny < m and arr_0[nx][ny] == 0 and (arr[nx][ny] == "-" or arr[nx][ny] == "E"):
               queue.append([nx, ny, queue[0][-1] + 1])
               arr_0[nx][ny] = 1
       queue.pop(0)
   while len(queue) == 0:
       print(-1)
       break
   t -= 1