题解 | 迷宫问题

from collections import deque
'''import sys
h,w=map(int,input().split())
maze=[list(map(int,input().split())) for _ in range(h)]
visited=[[False]*w for _ in range(h)]
path=[]
#print(maze)
def dfs(x,y):
    if (not (x>=0 and x<h and y>=0 and y<w) or visited[x][y]==True or maze[x][y]!=0):
        return False
    path.append((x,y))
    visited[x][y]=True
    if(x==h-1 and y==w-1):
        return True
    for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        #print(dx,dy)
        if(dfs(x+dx,y+dy)):
            return True
    path.pop()
    return False
dfs(0,0)
for x,y in path:
    print('('+str(x)+','+str(y)+')')'''

import sys
h,w = map(int,input().split())
maze=[list(map(int,input().split())) for _ in range(h)]
visited=[[False]*w for _ in range(h)]
parent=[[None]*w for _ in range(h)]
def bfs():
    queue= deque()
    queue.append((0,0))
    visited[0][0]=True
    while(queue):
        x,y=queue.popleft()
        if(x==h-1 and y==w-1):
            break
        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            #print(dx,dy)
            nx,ny=x+dx,y+dy
            #print(nx,ny)
            if(nx>=0 and nx<h and ny>=0 and ny<w) and maze[nx][ny]==0 and visited[nx][ny]==False:
                visited[nx][ny]=True
                queue.append((nx,ny))
                parent[nx][ny]=(x,y)
    x,y=h-1,w-1
    path=[]
    while ((x,y)!=(0,0)):
        path.append((x,y))
        x,y=parent[x][y]
    path.append((0,0))
    path.reverse()
    return path
path=bfs()
for x,y in path:
    print(f'({x},{y})')

注释的是DFS，下面是BFS。

BFS是最短路径，DFS不是。

DFS比较好写，一个递归调用。

BFS麻烦点