841.Keys and Rooms
===

###### tags: `Medium`,`DFS`,`BFS`,`Graph`

[841. Keys and Rooms](https://leetcode.com/problems/keys-and-rooms/)

### 題目描述

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

### 解答

#### C#

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
        bool[] unlocked = new bool[rooms.Count];
        unlocked[0] = true;

        Stack<int> roomKeys = new();
        roomKeys.Push(0);

        while (roomKeys.Count > 0) {
            int roomKey = roomKeys.Pop();
            foreach(int key in rooms[roomKey]) {
                if (!unlocked[key]) {
                    unlocked[key] = true;
                    roomKeys.Push(key);
                }
            }
        }
        
        return unlocked.All(unlock => unlock);
    }
}

>[name=Jim][time=Dec 20, 2022]

#### Javascript

function canVisitAllRooms(rooms) {
  const visited = new Array(rooms.length).fill(false);
  const stack = [0];

  while (stack.length) {
    const current = stack.pop();
    if (visited[current]) continue;
    visited[current] = true;
    stack.push(...rooms[current]);
  }

  for (let i = 0; i < rooms.length; i++) {
    if (!visited[i]) return false;
  }

  return true;
}

用Set寫了一個，感覺比較簡潔，但不會比較快。

function canVisitAllRooms2(rooms) {
  const stack = [0];
  const visited = new Set();

  while (stack.length) {
    const current = stack.pop();
    if (visited.has(current)) continue;
    visited.add(current);
    stack.push(...rooms[current]);
  }

  return visited.size === rooms.length;
}

>[name=Marsgoat][time=Dec 20, 2022]

#### Python

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        self.keys = {0}
        self.visited = set()

        def dfs(idx):
            for i in range(len(rooms)):
                if i in self.keys and i not in self.visited:
                    if i != 0 and i == idx:
                        continue
                    self.visited.add(i)
                    for key in rooms[i]:
                        self.keys.add(key)
                    dfs(i + 1)

        dfs(0)
        return len(self.visited) == len(rooms)

>[name=Kobe][time=Dec 20, 2022]

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        keys = set()
        keys.add(0)
        room_done =  set() 
        while len(keys-room_done) > 0:
            for room in keys-room_done:
                for key in rooms[room]:
                    keys.add(key)
                room_done.add(room)            
        return len(room_done) == len(rooms)

>[name=gp][time=Dec 20, 2022]

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        keys = [0]
        used_key = set()
        while len(keys) and len(used_key) != len(rooms):
            current_key = keys.pop()
            if current_key in used_key:
                continue
            keys = rooms[current_key] + keys
            used_key.add(current_key)
            #print(used_key)

        
        if len(used_key) != len(rooms):
            return False
        return True

>[name=玉山][time=Dec 21, 2022]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)