841.Keys and Rooms

tags: Medium,DFS,BFS,Graph

841. 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);
    }
}

JimDec 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;
}

MarsgoatDec 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)

KobeDec 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)

gpDec 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

玉山Dec 21, 2022

Reference

回到題目列表