题解 | 迷宫问题

栈的基本用法

from collections import deque

h, w = map(int, input().split())

map_graph = []
for _ in range(h):
    map_graph.append(list(map(int, input().split())))

p = [0, 0]  # 起始点
dfs = deque()  # 深度优先 [当前位置, 前进点位置, [未探索位置]]

# 获取当前可以走的范围
def check_direction(p, last_p):
    u, d, l, r = [None] * 4
    if p[0] > 0:
        u = [p[0]-1, p[1]]
    if p[0] < h-1:
        d = [p[0]+1, p[1]]
    if p[1] > 0:
        l = [p[0], p[1]-1]
    if p[1] < w-1:
        r = [p[0], p[1]+1]
    directions = [u, d, l, r]
    target_point = []
    for each in directions:
        if each is None:
            continue
        if each[0] == last_p[0] and each[1] == last_p[1]:  # 如果是上一步的位置，则跳过
            continue
        if not map_graph[each[0]][each[1]]:
            target_point.append(each)
    return target_point

# 搜索所有路口的走法
last_p = [0, 0]
while not (p[0] == h-1 and p[1] == w-1):
    can_go_point = check_direction(p, last_p)
    if len(can_go_point) > 1:
        last_p = p.copy()
        next_point = can_go_point.pop()
        dfs.append([p.copy(), next_point, can_go_point])
        p = next_point
    elif len(can_go_point) == 0:
        while len(can_go_point) == 0:
            p, _, can_go_point = dfs.pop()
        last_p = p.copy()
        next_point = can_go_point.pop()
        dfs.append([p.copy(), next_point, can_go_point])
        p = next_point
    else:
        last_p = p.copy()
        p = can_go_point.pop()

# 还原路口的走法（节约内存，消耗时间）
p = [0, 0]
last_p = [0, 0]
steps = []
while not (p[0] == h-1 and p[1] == w-1):
    can_go_point = check_direction(p, last_p)
    if len(can_go_point) > 1:
        last_p = p
        p, next_point, _ = dfs.popleft()
        steps.append(p)
        p = next_point
    elif len(can_go_point) == 0:
        raise Exception("NO!")
    else:
        last_p = p
        steps.append(p)
        p = can_go_point.pop()
steps.append(p)

for each in steps:
    print(f"({each[0]},{each[1]})")