题解 | 迷宫问题

import sys

#深度优先搜索 向其中传输：坐标值，网格表l，路径列表road，方向列表direc，以及已到访过的visited
def dfs(x,y,l,road,direc,visited):
  #当x,y到达目的地时，记录其坐标，返回True
    if x == h-1 and y == w-1:
        road.append((x,y))
        return True
    
	#现在从0,0开始，每到访过一个地方，就把visited变成True，并把当前位置记录
    visited[x][y] = True
    road.append((x,y))
    
	#对于当前位置，遍历右下左上四个方向的格子
    for dx,dy in direc:
        nx,ny = x+dx, y+dy
        if 0 <= nx < h and 0 <= ny < w:
		  #如果满足可以走（==0）且没走过（not visited）那就对它也深度优先搜索
            if l[nx][ny] == 0 and not visited[nx][ny]:
                if dfs(nx,ny,l,road,direc,visited):
                    return True
    
	#如果当前位置的四周都遍历完了，没有地方可走，就从当前位置退出（返回上一层函数）
	road.pop()
    visited[x][y] = False
    return False

h,w = map(int,input().split())
l=[]
for i in range(h):
    l.append(list(map(int,input().split())))

visited = [ [False for _ in range(w)] for _ in range(h) ]
direc = [(0,1),(1,0),(-1,0),(0,-1)]
road = []

if dfs(0,0,l,road,direc,visited):
    for i in road:
        print("({},{})".format(i[0],i[1]))