为何我的OBI蚂蚁滑行题Python代码陷入无限输入等待？

输出格式 #

输出一个整数，即蚁后最多能访问的大厅数量。

原运行代码 #

S, T, P = map(int, input().split())

A = {tunel + 1: altura for tunel, altura in enumerate(map(int, input().split()))}

conex = [set(map(int, input().split())) for tunel in range(T)]

A = {altura: tunel for tunel, altura in A.items() if altura <= A[P]}
A = {tunel: altura for altura, tunel in A.items()}
A = sorted(A.items(), reverse=True, key=lambda kv: (kv[1], kv[0]))

res = 0
while 1:
    try:
        sala_1 = A[0]
        sala_2 = A[1]

        if {sala_1[0], sala_2[0]} in conex:
            res += 1
        else:
            del sala_2
            continue
    except IndexError:
        break

    del sala_1

print(res)

问题情况 #

原本代码运行正常，但将代码中else块修改为以下内容后，运行时输入完所有数据程序持续无响应（看似等待输入，实际为逻辑死循环）：

else:
    del sala_2
    break

问题根源 #

1. 变量删除逻辑错误：原代码中del sala_2仅删除了变量sala_2的引用，并未修改列表A的内容。当两个大厅无隧道连接时，continue会让循环重复读取相同的A[0]和A[1]，直接触发无限循环。之前程序正常是因为测试用例未触发该场景。
2. 核心逻辑偏离题目要求：代码按高度排序后检查相邻大厅的连接数，这和题目要求的“求最长滑行路径长度”完全不符，本质是逻辑错误。

修复方案 #

要正确解决题目，需使用记忆化DFS计算每个大厅能到达的最远距离，符合“从高到低滑行”的规则：

正确代码示例 #

S, T, P = map(int, input().split())
heights = list(map(int, input().split()))
# 转为1-based索引，匹配大厅编号
heights = [0] + heights
# 构建邻接表，仅保留可滑行的方向（高→低）
adj = [[] for _ in range(S+1)]
for _ in range(T):
    u, v = map(int, input().split())
    if heights[u] > heights[v]:
        adj[u].append(v)
    elif heights[v] > heights[u]:
        adj[v].append(u)

# 记忆化数组，存储每个大厅能到达的最大数量
memo = [0]*(S+1)

def dfs(node):
    if memo[node] != 0:
        return memo[node]
    max_count = 0
    for neighbor in adj[node]:
        max_count = max(max_count, 1 + dfs(neighbor))
    memo[node] = max_count
    return max_count

print(dfs(P))

代码说明 #

• 邻接表构建：仅保留从高大厅到低大厅的路径，严格符合题目滑行规则；
• 记忆化DFS：避免重复计算相同大厅的路径长度，高效求解起始大厅能到达的最大大厅数量。

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