python 非递归bfs

解题思路:

求这种最短路径的迷宫问题基本上都可以用bfs来解决

注意事项:

这个地方需要记录路径，因此我们需要用到copy包中的deepcopy()

参考代码:

from copy import deepcopy

def maze(A):
   queue=[[0,0,[]]]
   visited=[[False for _ in range(5)] for __ in range(5)]
   dx = [1, -1, 0, 0]
   dy = [0, 0, 1, -1]
   visited[0][0]=True
   while queue:
       obj=queue.pop(0)
       i=obj[0]
       j=obj[1]
       road=deepcopy(obj[2])

       if i==4 and j==4:
           return road

       for x in range(4):
           di=i+dx[x]
           dj=j+dy[x]
           if di>=0 and dj<5 and di<5 and dj>=0:
               if visited[di][dj]==False and A[di][dj]!=1:
                   visited[di][dj]=True
                   B=deepcopy(road)
                   B.append([di,dj])
                   queue.append([di,dj,B])

A=[]
for i in range(5):
   A.append(list(map(int,input().split())))

print((0,0))
for i in maze_2(A):
   print(tuple(i))