基于广度优先遍历

1. 最短路径遍历到后程序结束；
2. 需要记录下路径

def maze_solution(nx, ny, maze):
    visited = set()
    # 全局队列
    Q = [(0, 0)]
    # 当前队列
    q = []
    # 最短路径
    path = []
    # 可以移动的方向
    directions = (
        (0, 1),
        (0, -1),
        (1, 0),
        (-1, 0)
    )

    while Q:
        while Q:
            x, y = Q.pop(0)
            if (x, y) not in path:
                path.append((x, y))
            if x == nx - 1 and y == ny - 1:
                # 返回最短路径
                # 重建路径
                cur = (x, y)
                tmp = [cur]
                for i in range(len(path) - 1, 0, -1):
                    x2, y2 = path[i - 1]
                    x1, y1 = cur
                    for dx, dy in directions:
                        if x2 == x1 + dx and y2 == y1 + dy:
                            tmp.insert(0, (x2, y2))
                            cur = (x2, y2)
                # print(path)
                return tmp
            else:
                for dx, dy in directions:
                    new_x, new_y = x + dx, y + dy
                    if (new_x, new_y) not in visited and 0 <= new_x < nx and 0 <= new_y < ny and maze[new_x][new_y] == 0:
                        # 将当前point记录到访问集合
                        visited.add((new_x, new_y))
                        # 本轮可移动的路径均记录在q
                        q.append((new_x, new_y))
        # 取出当前轮的其他路径继续遍历
        while q:
            Q.append(q.pop(0))


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

for item in maze_solution(nx, ny, maze):
    print(f'({item[0]},{item[1]})')