[LeetCode] 841. Keys and Rooms

841. Keys and Rooms

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: Depth-First Search、Breadth-First Search、Graph

一、題目

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example 1:

• Input: rooms = [[1],[2],[3]]
• Output: true
• Explanation: We visit room 0 and pick up key 1.
  We then visit room 1 and pick up key 2.
  We then visit room 2 and pick up key 3.
  We then visit room 3.
  Since we were able to visit every room, we return true.

Example 2:

• Input: rooms = [[1,3],[3,0,1],[2],[0]]
• Output: false
• Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Constraints:

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• All the values of rooms[i] are unique.

二、分析

• 典型的 Graph 問題，利用 visited 來記錄拜訪過了沒，並用 BFS 來遍歷整個 Graph，每次拜訪一間新的 room 時，將 key 加入到新的佇列中，看是否能能遍歷整個 graph。

三、解題

1. BFS

• Time complexity: \(O(n)\)
• Space complexity: \(O(n)\)

bool canVisitAllRooms(vector<vector<int>>& rooms) {
    queue<int> q;
    q.push(0);
    int cnt = rooms.size();
    vector<bool> used(rooms.size(), false);
    while (!q.empty()){
        int key = q.front();
        q.pop();
        if (used[key]) continue;
        cnt--;
        if (cnt == 0) break;
        used[key] = true;
        for (int next : rooms[key]){
            if (used[next]) continue;
            q.push(next);
        }
    }
    return cnt == 0;
}

回目錄 Catalog