Keys And Rooms Problem


Description

LeetCode Problem 841.

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:

1
2
3
4
5
6
7
8
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:

1
2
3
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.


Sample C++ Code

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
class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<int> visited(n, 0);
        visited[0] = 1;
        int r;
        
        stack<int> st;
        st.push(0);
        
        while (!st.empty()) {
            r = st.top();
            st.pop();
            for (int i = 0; i < rooms[r].size(); i ++) {
                if (visited[rooms[r][i]] == 0) {
                    visited[rooms[r][i]] = 1;
                    st.push(rooms[r][i]);
                }
            }
        }
        
        for (auto v : visited) {
            if (v == 0)
                return false;
        }
        return true;
    }
};




Related Posts

Vertical Order Traversal Of A Binary Tree Problem

LeetCode 987. Given the root of a binary tree, calculate...

Univalued Binary Tree Problem

LeetCode 965. A binary tree is uni-valued if every node...

Sum Of Distances In Tree Problem

LeetCode 834. There is an undirected connected tree with n...

Smallest Subtree With All The Deepest Nodes Problem

LeetCode 865. Given the root of a binary tree, the...

Smallest String Starting From Leaf Problem

LeetCode 988. You are given the root of a binary...

Similar String Groups Problem

LeetCode 839. Two strings Xand Yare similar if we can...