841.钥匙和房间

发表于： 分类于：
字数： 862 阅读：≈ 2分钟

🗝️ 841.钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

思路

基本思想

只能从0号房间开始，相当于从0开始向后扩散，越来越大，这个扩散的过程形成了一个有向图，每走到一个节点，能进入的房间都会非递减的增长，所以只需要统计哪些房间可以进入，进入之后拿到钥匙，范围扩大到了哪

关键点就是记录这个范围，初始记录所有的房间都无法访问，然后从0号房间开始出发，进行深度搜索，每到一个房间都拿出房间中的钥匙，然后用这些钥匙去指定的房间，遇到访问过的房间就去下一间

执行流程

  1. 从0号房间出发，拿到0号房间中放置的钥匙
  2. 去对应的房间开锁，拿到对应房间的钥匙
  3. 重复2，直到遇到已经进入过的房间
  4. 一层一层向下，偶尔回溯

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited (rooms.size(),false);
        //需要以0号房间为起点
        dfs(visited,0,rooms);
        //查看是否有房间没被访问
        for(int i=0;i<visited.size();++i){
            if(!visited[i]){//有房间没被访问
                return false;
            }
        }
        //所有的房间都被访问
        return true;
    }
    //注意要传递引用
    void dfs(vector<bool> &visited,int key,vector<vector<int>> rooms){
        if(visited[key]){//当前房间有钥匙，但是被访问过了
            return;
        }
        //当前房间有钥匙没被访问
        visited[key]=true;
        //进入当前房间，拿到当前房间的钥匙
        vector<int> keys =rooms[key];
        //拿到钥匙之后，递归向下，目的是使用所有的钥匙
        for(int key:keys){
            dfs(visited,key,rooms);
        }
    }
};

总结

主要是进入一个房间之后，拿到这些钥匙，就依次进入对应的房间，然后再从这个房间拿到对应的钥匙，没进入一个房间拿到对应的钥匙，都设置一个for循环，目的是使用拿到的钥匙去打开所有的房间，这样所有的钥匙都会被使用

最后查看是否有房间没被打开，有的话说明即使全部钥匙都使用了，但还是无法进入所有房间