题解 | #迷宫问题#

def find(x, y): #查找从（x,y）到终点的路径
    dx = [-1, 1, 0, 0] #每次移动一点，x坐标的变化
    dy = [0, 0, 1, -1] #每次移动一点，y坐标的变化，顺序并不会影响，只要x,y都遍历1， -1， 0， 0就可以
    if x == m-1 and y == n-1:
        #判定到达goal，输出路线
        for i in route:
            print("(" + str(i[0]) + "," + str(i[1]) + ")")#注意int要转化成str
        return
    for i in range(4):
        xr = x + dx[i]#每次x或y移动一格（1或-1），注意用新的xr储存，不能直接在x上做运算，否则下个循环x就不是初始值了
        yr = y + dy[i]
        #注意判定xr和yr是否是在矩阵范围内的，并且矩阵值为0，没有被访问过
        if xr>=0 and xr<m and yr>=0 and yr<n and map1[xr][yr] == 0:
            map1[xr][yr] = 1 #设定被访问过
            route.append((xr,yr)) #记录路径
            find(xr, yr) #用递归的方法继续搜索
            # 回溯，把矩阵值清零，把路径去掉新加入的点，路径相当于栈
            map1[x][y] = 0
            route.pop()
while True:
    try:
        m, n = map(int, input().split())
        map1 = [] #用矩阵储存每个点0或者1,0是可以走的路线，1是墙或者走过的路线
        for i in range(m):
            map1.append(list(map(int, input().split())))
        route = [(0, 0)] # 经过的路径点记录
        map1[0][0] = 1 #先把起点设为走过的地方
        find(0, 0) #用recursion递归，回溯的方式查找从起点到终点的路径
    except Exception:
        break