[LeetCode] 841. 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. html

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.git

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

You can walk back and forth between rooms freely.函数

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

Example 1:url

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:spa

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:code

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

这道题给了咱们一些房间，房间里有一些钥匙，用钥匙能够打开对应的房间，说是起始时在房间0，问最终是否能够打开全部的房间。这不禁得让博主想起了惊悚片《万能钥匙》，还真是头皮发麻啊。赶忙扯回来，这是一道典型的有向图的遍历的题，邻接链表都已经创建好了，这里直接遍历就行了，这里先用 BFS 来遍历。使用一个 HashSet 来记录访问过的房间，先把0放进去，而后使用 queue 来辅助遍历，一样将0放入。以后进行典型的 BFS 遍历，取出队首的房间，而后遍历其中的全部钥匙，若该钥匙对应的房间已经遍历过了，直接跳过，不然就将钥匙加入 HashSet。此时看若 HashSet 中的钥匙数已经等于房间总数了，直接返回 true，由于这表示全部房间已经访问过了，不然就将钥匙加入队列继续遍历。最后遍历结束后，就看 HashSet 中的钥匙数是否和房间总数相等便可，参见代码以下：orm

解法一：htm

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

咱们也可使用递归的解法来作，仍是使用 HashSet 来记录访问过的房间，递归函数还须要传进当前的房间，还有 HashSet，首先将当前房间加入 HashSet，而后遍历此房间中的全部钥匙，若是其对应的房间没有访问过，则调用递归函数，参见代码以下：

解法二：

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/841

参考资料：

https://leetcode.com/problems/keys-and-rooms/

https://leetcode.com/problems/keys-and-rooms/discuss/133944/Java-8-lines

https://leetcode.com/problems/keys-and-rooms/discuss/133855/Straight-Forward

LeetCode All in One 题目讲解汇总(持续更新中...)