LeetCode – Keys and Rooms

题目：

There are N rooms and you start in room 0.  Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length.  A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input:

[[1],[2],[3],[]]

Output:

true

Explanation:

We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input:

[[1,3],[3,0,1],[2],[0]]

Output:

false

Explanation:

We can't enter the room with number 2.

Note:

1. 1 <= rooms.length <= 1000
2. 0 <= rooms[i].length <= 1000
3. The number of keys in all rooms combined is at most 3000.

解题：

BFS方式，借助队列和Hash表实现：

1. 放入第0号分房间队列，并初始化为已访问 ；
2. 取出队列首的房间取出其中的钥匙；
3. 通过visited Hash表判断，如果钥匙对应房间已经访问，取下一把钥匙；
4. 通过visited Hash表判断，如果对应房间未访问，设置为已访问；
5. 如果访问的房间数等于房间总数返回true；
6. 如果访问的房间数未达到房间总数， 放入队列继续遍历；
7. 遍历结束后判断visited中存放的钥匙和房间数是否相等判断完全遍历。

实现：

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        unordered_set<int> visited{{0}};
        queue<int> q{{0}};
        while (!q.empty()){
            int no = q.front(); 
            q.pop();
            for (int key : rooms[no]){
                if (visited.count(key) > 0) continue;
                visited.insert(key);
                if (visited.size() == rooms.size()) return true;
                q.push(key); 
            }
        }
        return visited.size()== rooms.size();
        
    }
};

解题：

DFS递归调用，借助Hash表实现：

1. 递归函数放入rooms， 当前0号房间，以及Hash表 ；
2. 取出队列首的房间取出其中的钥匙；
3. 递归调用函数visitNextRoom完成访问；
4. 结束后判断是否已经完全遍历。

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        unordered_set<int> visited;
        visitNextRooms(rooms, 0, visited);
        return (visited.size() == rooms.size());
        
    }
    void visitNextRooms(vector<vector<int>>& rooms, int curkey, unordered_set<int>& visited ) {
        visited.insert(curkey);
        for (int key: rooms[curkey]){
            if (!visited.count(key)) visitNextRooms(rooms, key, visited);
        }
        
    }
};

参考：

[LeetCode] 841. Keys and Rooms 钥匙与房间

Photo by Vecislavas Popa from Pexels