Python实现矩阵DFS寻路遇墙递归错误问题排查

触发RecursionError的核心原因 #

• 越界校验逻辑写错：当前代码判断坐标是否在矩阵合法范围内时，校验的是当前位置l,c，而非下一步要移动到的nextl,nextc，走到矩阵边缘时会访问不存在的索引，逻辑错乱后进入无效递归。
• 传送门场景存在无限循环：代码仅将传送门入口加入路径队列Q做已访问标记，传送后的出口坐标未做重复访问校验，极易出现「踩A传送门到B点→走回B传送门回到A点」的来回跳转，递归栈深度超过上限直接报错。
• 方向参数p的作用域错误：遍历方向的for循环中直接修改外层的p变量，死路回溯时p不会恢复为进入当前节点的初始值，导致方向判断锁死，反复沿同一条无效路径递归。

搜索结果依赖方向顺序的核心原因 #

• 已访问标记逻辑不完整，部分节点漏标记、部分节点重复遍历，实现的不是严格的深度优先搜索，本质是沿方向优先级随机探路，先遍历的方向碰巧绕到终点就返回成功，先撞进逻辑死胡同就直接判失败，结果自然和方向顺序强绑定。
• 传送门穿越后的方向继承逻辑分支冗余，部分合法路径被错误拦截，进一步放大了方向顺序的影响。
• 矩阵预处理时用M.index(i)、i.index(h)找坐标的写法有bug，如果矩阵存在重复行/重复元素，会拿到错误的坐标值，导致墙体、通路、传送门、终点的位置识别错误。

• 所有坐标合法性校验统一针对下一步坐标nextl,nextc执行，校验通过后再访问矩阵对应位置的值。
• 简化传送门逻辑：踩到传送门时直接计算出口坐标，将入口加入已访问路径后，直接从出口位置继续搜索，不要给传送门写单独的递归分支。
• 遍历方向时使用临时变量存储方向值，不要修改函数入参p，回溯时临时值自动丢弃，不会污染其他方向的判断逻辑。
• 矩阵预处理时用行号、列号的遍历索引直接赋值，不要用index()方法查找坐标，避免定位错误。
• 补全代码语法错误：print("Success"缺失右括号。

def portal(M, l, c, D):
    current_val = M[l][c]
    pos1, pos2 = D[current_val]
    return pos2 if [l, c] == pos1 else pos1

def dfs(M, Q, target, D, p_dir=0):
    l, c = Q[-1]
    if [l, c] == target:
        return True
    # 四个方向：北、西、东、南，对应方向编号1/2/3/4
    dirs = [(-1, 0, 1), (0, -1, 2), (0, 1, 3), (1, 0, 4)]
    for dl, dc, dir_id in dirs:
        # 穿越传送门时仅允许沿原方向前进
        if p_dir != 0 and dir_id != p_dir:
            continue
        nextl, nextc = l + dl, c + dc
        # 先校验下一步坐标是否越界
        if not (0 <= nextl < len(M) and 0 <= nextc < len(M[0])):
            continue
        next_val = M[nextl][nextc]
        # 撞墙直接跳过
        if next_val == 0:
            continue
        # 踩到传送门，计算出口坐标
        if next_val in D:
            # 入口已访问则跳过，避免循环
            if (nextl, nextc) in Q:
                continue
            Q.append((nextl, nextc))
            exit_l, exit_c = portal(M, nextl, nextc, D)
            # 出口已访问则回溯
            if (exit_l, exit_c) in Q:
                Q.pop()
                continue
            Q.append((exit_l, exit_c))
            # 穿传送门后保留原方向继续搜索
            if dfs(M, Q, target, D, dir_id):
                return True
            Q.pop()
            Q.pop()
        # 普通通路或终点
        else:
            if (nextl, nextc) in Q:
                continue
            Q.append((nextl, nextc))
            # 普通路径移动后重置方向参数，允许四个方向探索
            if dfs(M, Q, target, D, 0):
                return True
            Q.pop()
    return False

# 主逻辑
if __name__ == "__main__":
    L = int(input())
    M = []
    for _ in range(L):
        M.append(input().split())
    D = {}
    COORD = None
    # 预处理矩阵，直接用遍历索引定位，避免index()的定位错误
    for line_idx in range(L):
        line = M[line_idx]
        for col_idx in range(len(line)):
            val = line[col_idx]
            if val == "#":
                M[line_idx][col_idx] = 0
            elif val == ".":
                M[line_idx][col_idx] = 1
            elif val == "*":
                COORD = [line_idx, col_idx]
            else:
                # 记录传送门坐标
                if val in D:
                    D[val].append([line_idx, col_idx])
                else:
                    D[val] = [[line_idx, col_idx]]
    l0, c0 = map(int, input().split())
    queue = [(l0, c0)]
    if dfs(M, queue, COORD, D):
        print("Success")
    else:
        print("Failure")

内容的提问来源于stack exchange，提问作者throwaway33