题解 | #迷宫问题#回溯遍历

y_size, x_size = [int(x) for x in input().split()]
board = []
while True:
    try:
        line = [int(x) for x in input().split()]
        board.append(line)
    except:
        break
#判断路径落点是否在迷宫内
def isValid(x, y):
    if x>=0 and x<=x_size-1:
        if y>=0 and y<=y_size-1:
            return True
    return False
#步骤1：确认入口参数为迷宫，横坐标，纵坐标，当前路径，上一次移动方向；找到一条路径立即返回，因此需要有返回值
def searchRoad(board, x, y, path, pre_dir):
	#步骤2：回溯终止条件为到达迷宫出口
    if x==x_size-1 and y==y_size-1:
        for move in path:
            print("({},{})".format(move[0],move[1]))
        return True
    #步骤3：单层递归逻辑本质上是遍历四叉树，传入上一次移动方向防止进入死循环
    if isValid(x+1, y) and board[y][x+1]==0 and pre_dir!="Left":
        path.append([y, x+1])
        if searchRoad(board, x+1, y, path, "Right"): return True
        path.pop()
    if isValid(x, y+1) and board[y+1][x]==0 and pre_dir!="Up":
        path.append([y+1, x])
        if searchRoad(board, x, y+1, path, "Down"): return True
        path.pop()
    if isValid(x-1, y) and board[y][x-1]==0 and pre_dir!="Right":
        path.append([y, x-1])
        if searchRoad(board, x-1, y, path, "Left"): return True
        path.pop()
    if isValid(x, y-1) and board[y-1][x]==0 and pre_dir!="Down":
        path.append([y-1, x])
        if searchRoad(board, x, y-1, path, "Up"): return True
        path.pop()
searchRoad(board, 0, 0, [[0,0]], "None")