题解 | #迷宫问题#

#bfs
#为什么元祖放入字典里多一个空格   （0,0）-> (0, 0)?
dirs = [(0,1),(1,0),(0,-1),(-1,0)]	#四个方向
queue = []  
def mark(maze,pos):		#标记走过的
    maze[pos[0]][pos[1]] = 2 

def bfs(maze,start):
    queue.append(start)
    mark(maze, start)
    parent = {start:None}	#接收前一个点
    while len(queue) > 0:
        pos = queue.pop(0)
        for i in range(4):
            nextp = (pos[0] + dirs[i][0],pos[1] + dirs[i][1])
            if 0 <= nextp[0] < m and 0 <= nextp[1] < n and maze[nextp[0]][nextp[1]] == 0:
                mark(maze,nextp)
                queue.append(nextp)
                parent[nextp] = pos
    return parent

lst = input().split()
m,n = int(lst[0]),int(lst[1])
maze,paths = [],[]
for i in range(m):
    maze.append(list(map(int,input().split())))
start,end = (0,0),(m-1,n-1)
parent = bfs(maze,start)
while end != None: #逆向输出得到路径
    paths.insert(0,end)
    end = parent[end]
for i in paths:
    print(str(i).replace(' ',''))	#输出元祖会报错，多了一个空格，然而我并不知道为什么会多个空格。求解！