(图论) 841. 钥匙和房间 ——【Leetcode每日一题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了(图论) 841. 钥匙和房间 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❓ 841. 钥匙和房间

难度：中等

有 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 == roo m s . l e n g t h$
$2 <= n <= 1000$
$0 <= roo m s [i] . l e n g t h <= 1000$
$1 <= s u m (roo m s [i] . l e n g t h) <= 3000$
$0 <= roo m s [i] [j] < n$
所有 $roo m s [i]$ 的值互不相同

💡思路：

可以将每个房间当作图中的结点，钥匙当作图中的边，只要所有结点能够连通，则返回true;

法一：BFS

数组 rooms 的长度即为房间的总个数：(bfs)

可以设置一个数组 open，记录是否找到钥匙；
以及一个队列 keys，存储在每个房间取得的钥匙;
再另设一个变量 count 记录已打开房间的个数，最后只需比较 count 是否等于房间的总个数。

法二：DFS

我们可以使用深度优先搜索的方式遍历整张图，

统计可以到达的节点个数，并利用数组 open 标记当前节点是否访问过，以防止重复访问。

🍁代码：(C++、Java)

法一：BFS
C++

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        queue<int> keys;
        vector<int> open(rooms.size());
        open[0] = 1;
        int count = 1;
        for(int k : rooms[0]){
            keys.push(k);
        }
        while(!keys.empty()){
            int key = keys.front();
            keys.pop();
            if(open[key] == 0){
                for(int k : rooms[key]){
                    keys.push(k);
                }
                open[key] = 1;
                count++;
            }
        }
        return count == rooms.size();
    }
};

Java

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Queue<Integer> keys = new LinkedList();
        int[] open = new int[rooms.size()];
        open[0] = 1;
        int count = 1;
        for(int k : rooms.get(0)){
            keys.offer(k);
        }
        while(!keys.isEmpty()){
            int key = keys.poll();
            if(open[key] == 0){
                for(int k : rooms.get(key)){
                    keys.offer(k);
                }
                open[key] = 1;
                count++;
            }
        }
        return count == rooms.size();
    }
}

法二：DFS
C++

class Solution {
private:
    void dfs(const vector<vector<int>>& rooms, int key, vector<int>& open){
        if(open[key] == 1) return;
        open[key] = 1;
        for(int k : rooms[key]){
            dfs(rooms, k, open);
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> open(rooms.size());
        dfs(rooms, 0, open);
        for(int p : open){
            if(p == 0) return false;
        }
        return true;
    }
};

Java

class Solution {
    private void dfs(List<List<Integer>> rooms, int key, int[] open){
        if(open[key] == 1) return;
        open[key] = 1;
        for(int k : rooms.get(key)){
            dfs(rooms, k, open);
        }
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] open = new int[rooms.size()];
        dfs(rooms, 0, open);
        for(int p : open){
            if(p == 0) return false;
        }
        return true;
    }
}