题解 | #迷宫问题#

# 判断一个点是否合法，
def isOK(x,y):
    if 0 <= x < n and 0 <= y < m and maze[x][y] == 0:
        return True
    else:
        return False

n,m = list(map(int,input().split()))
maze = []
for i in range(n):
    maze.append(list(map(int,input().split())))

# 使用队列思想表示当前处于搜索状态的点，同时使用列表表示点前后间的转移
PointList = [(0,0)]
fatherPointList = [(0,0)]
maze[0][0] = 2
# 使用指针表示当前判断的位置
Point = 0
# 如果当前位置周边有合适的点位，则新增相邻合法点位到 PointList 中，并将 Point 右移1位，同时在 fatherPointList 对应位置添加表示新增点位的上一跳
# 如果当前位置周边没有合适点位，则仅将 Point 右移1位
while Point < len(PointList):
    x,y = PointList[Point][0],PointList[Point][1]
    # 判断是否到终点
    if x == n-1 and y == m-1:
        break
    if isOK(x-1,y):
        PointList.append((x-1,y))
        fatherPointList.append((x,y))
        maze[x-1][y] = 2
    if isOK(x+1,y):
        PointList.append((x+1,y))
        fatherPointList.append((x,y))
        maze[x+1][y] = 2
    if isOK(x,y-1):
        PointList.append((x,y-1))
        fatherPointList.append((x,y))
        maze[x][y-1] = 2
    if isOK(x,y+1):
        PointList.append((x,y+1))
        fatherPointList.append((x,y))
        maze[x][y+1] = 2
    Point += 1
# 到达终点后，回溯其路径
path = [(n-1,m-1)]
while path[0] != (0,0):
    path.insert(0,fatherPointList[PointList.index(path[0])])
for location in path:
    print('(%d,%d)'%(location[0],location[1]))


'''
# 使用栈思想表示路径
stack = [(0,0)]
maze[0][0] = 2
while len(stack) > 0:
    # x,y 分别表示 行,列
    x,y = stack[-1][0],stack[-1][1]
    # 判断是否到终点
    if x == n-1 and y == m-1:
        break
    # 遍历一个点周边的四个点，判断是否出界、是否为1、是否为2（已经走过）、是否为0（可以走），如果均不能走则回退
    if isOK(x-1,y):
        stack.append((x-1,y))
        maze[x-1][y] = 2
    elif isOK(x+1,y):
        stack.append((x+1,y))
        maze[x+1][y] = 2
    elif isOK(x,y-1):
        stack.append((x,y-1))
        maze[x][y-1] = 2
    elif isOK(x,y+1):
        stack.append((x,y+1))
        maze[x][y+1] = 2
    else:
        stack.pop()
for location in stack:
    print('(%d,%d)'%(location[0],location[1]))
'''