题解 | 迷宫问题

from collections import deque
h,w = map(int,input().split())
arr = []
graph = {}
for i in range(h):
    arr.append(list(map(int,input().split())))
directions = [(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if arr[i][j] == 0:
            for di,dj in directions:
                newi,newj = i + di,j + dj
                if 0 <= newi < h and 0 <= newj < w:
                    if arr[newi][newj] == 0:
                        if (i,j) not in graph:
                            graph[(i,j)] = [(newi,newj)]
                        else:
                            graph[(i,j)].append((newi,newj))
# print(graph)
def bfs(graph,start,end):
    visited = set()
    queue = deque([[start]])
    while queue:
        current_path = queue.popleft()
        current_node = current_path[-1]
        if current_node == end:
            return current_path
        if current_node not in visited:
            visited.add(current_node)
            # 遍历当前节点的所有邻居
            for neighbor in graph[current_node]:
                # 创建新路径
                new_path = list(current_path)
                new_path.append(neighbor)
                # 将新路径加入队列
                queue.append(new_path)
    return None
path = bfs(graph,(0,0),(h-1,w-1))
for node in path:
    print("("+str(node[0])+","+str(node[1])+")")