LeetCode 841钥匙和房间代码陷入死循环，求问题原因

死循环的核心原因 #

你代码里的队列存的是整个房间的钥匙列表，而且没有判断房间是否已被访问就重复添加，导致队列不断累积重复的钥匙列表，永远处理不完。举个例子：如果房间0的钥匙是[1]，处理后加入房间1的钥匙列表；要是房间1的钥匙包含[0]，就会把房间0的钥匙列表再次加入队列，这样队列里就循环出现[1]、[0]的钥匙列表，永远出不了循环。

你的代码具体问题 #

• 队列存储的是rooms[k]（整个房间的钥匙集合），而非单个房间号，导致每次处理的是一堆钥匙，而非一个房间
• 拿到钥匙k后直接标记dp[k]=1，但没检查这个房间是否已经被处理过，就直接把它的钥匙列表塞进队列，重复添加引发死循环

修正后的代码 #

from collections import deque
from typing import List

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        visited[0] = True
        queue = deque()
        # 初始把第一个房间的所有钥匙对应的房间号加入队列
        queue.extend(rooms[0])
        
        while queue:
            room_num = queue.popleft()
            if not visited[room_num]:
                visited[room_num] = True
                # 将当前房间的钥匙加入队列，等待处理
                queue.extend(rooms[room_num])
        
        # 检查是否所有房间都被访问过
        return all(visited)

修正要点 #

1. 队列改存房间号，每次处理单个房间，逻辑更清晰
2. 只有当房间未被访问时，才标记为已访问并将其钥匙对应的房间号加入队列，彻底避免重复添加
3. 用all(visited)直接判断是否所有房间都能访问，代码更简洁

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