Medium

题目描述

有 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 号房间，因为我们没有它的钥匙。

提示：

  • n == rooms.length
  • 2 <= n <= 1000
  • 0 <= rooms[i].length <= 1000
  • 1 <= sum(rooms[i].length) <= 3000
  • 0 <= rooms[i][j] < n
  • 所有 rooms[i] 的值 互不相同

解题思路

这是一个典型的图遍历问题，可以看作从节点 0 开始，判断是否能访问到所有节点。

思路分析：

  1. 问题建模：将房间看作图中的节点，钥匙看作有向边。从房间 0 开始，我们需要判断是否能够访问到所有房间。

  2. DFS 解法：从房间 0 开始深度优先搜索，用一个 visited 数组记录已访问的房间。对于当前房间中的每把钥匙，如果对应的房间还未访问过，则递归访问该房间。最后检查是否所有房间都被访问过。

  3. BFS 解法：使用队列进行广度优先搜索，同样用 visited 数组记录访问状态。将房间 0 加入队列，然后不断取出队首房间，访问其中的钥匙对应的未访问房间。

  4. 优化细节：

    • 使用 visited 数组避免重复访问
    • 可以用计数器记录已访问房间数，避免最后遍历整个 visited 数组
    • 提前终止：如果已访问房间数等于总房间数，可以直接返回 true

推荐解法：DFS 递归解法，代码简洁清晰，时间复杂度相同。

代码实现

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<bool> visited(n, false);
        dfs(rooms, 0, visited);
        
        for (bool v : visited) {
            if (!v) return false;
        }
        return true;
    }
    
private:
    void dfs(vector<vector<int>>& rooms, int room, vector<bool>& visited) {
        visited[room] = true;
        for (int key : rooms[room]) {
            if (!visited[key]) {
                dfs(rooms, key, visited);
            }
        }
    }
};

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        
        def dfs(room):
            visited[room] = True
            for key in rooms[room]:
                if not visited[key]:
                    dfs(key)
        
        dfs(0)
        return all(visited)

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
        int n = rooms.Count;
        bool[] visited = new bool[n];
        DFS(rooms, 0, visited);
        
        foreach (bool v in visited) {
            if (!v) return false;
        }
        return true;
    }
    
    private void DFS(IList<IList<int>> rooms, int room, bool[] visited) {
        visited[room] = true;
        foreach (int key in rooms[room]) {
            if (!visited[key]) {
                DFS(rooms, key, visited);
            }
        }
    }
}

var canVisitAllRooms = function(rooms) {
    const n = rooms.length;
    const visited = new Array(n).fill(false);
    
    const dfs = (room) => {
        visited[room] = true;
        for (const key of rooms[room]) {
            if (!visited[key]) {
                dfs(key);
            }
        }
    };
    
    dfs(0);
    return visited.every(v => v);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(N + M)N 是房间数，M 是钥匙总数，每个房间和每把钥匙都会被访问一次
空间复杂度O(N)visited 数组占用 O(N) 空间，递归调用栈最深为 O(N)

相关题目