LeetCode钥匙与房间问题求解：现有代码优化咨询

题目描述 #

有n个房间，编号从0到n-1，除房间0外所有房间均被锁住。目标是访问所有房间，但无对应钥匙无法进入锁住的房间。访问房间时可获得一组钥匙，每个钥匙对应可解锁的房间编号，可带走所有钥匙解锁其他房间。给定数组rooms，其中rooms[i]是访问房间i时能获得的钥匙集合，若能访问所有房间返回true，否则返回false。

示例1 #

输入: rooms = [[1],[2],[3],[]]
输出: true
解释: 访问房间0拿到钥匙1，接着访问房间1拿到钥匙2，再访问房间2拿到钥匙3，最后访问房间3，能访问所有房间，故返回true。

示例2 #

输入: rooms = [[1,3],[3,0,1],[2],[0]]
输出: false
解释: 无法进入房间2，因为打开它的唯一钥匙就在该房间内。

我编写的代码 #

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        hkey=[]
        count=0
        status=[False for i in range(len(rooms))]
        for i in rooms:
            for j in i:
                status[j]=True
        for i in range(len(status)):
            if status[i]==True:
                count+=1i
        if count==len(status)-1:
            return True
        else:
            return False

该代码仅能通过基础测试用例，无法覆盖所有场景，求优化方案。

原代码的核心问题 #

1. 逻辑错误：代码只是统计所有出现过的钥匙数量，完全忽略了「钥匙必须通过已访问的房间才能获取」这个核心规则。比如示例2中，房间2的钥匙仅存在于自身房间，代码会错误标记status[2] = True，但实际上根本无法拿到这把钥匙。
2. 语法错误：count += 1i是无效写法，应为count += 1。

正确解题思路：图遍历（DFS/BFS） #

这是典型的图遍历问题：每个房间是图的节点，钥匙代表节点间的可达边。我们需要从节点0出发，遍历所有可达节点，最后判断是否覆盖全部节点。

方案1：深度优先搜索（DFS） #

用递归实现，逐层深入访问可到达的房间：

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False] * len(rooms)
        
        def dfs(room_idx):
            visited[room_idx] = True
            # 遍历当前房间的所有钥匙
            for key in rooms[room_idx]:
                if not visited[key]:
                    dfs(key)
        
        # 从房间0开始遍历
        dfs(0)
        # 判断是否所有房间都被访问
        return all(visited)

方案2：广度优先搜索（BFS） #

用队列实现，按层处理可访问的房间：

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False] * len(rooms)
        queue = deque()
        # 初始加入房间0并标记已访问
        queue.append(0)
        visited[0] = True
        
        while queue:
            current_room = queue.popleft()
            # 处理当前房间的所有钥匙
            for key in rooms[current_room]:
                if not visited[key]:
                    visited[key] = True
                    queue.append(key)
        
        return all(visited)

代码说明 #

• 两个方案均用visited数组记录房间访问状态，初始仅房间0为已访问。
• DFS通过递归深入每个可访问房间，BFS通过队列依次处理每个房间的钥匙。
• 最终用all(visited)判断是否所有房间都被访问，是则返回True，否则返回False。

内容的提问来源于stack exchange，提问作者Rama Krishna Mandapaka