Pular para o conteúdo

Abrir todas as salas trancadas

Fácil#dfs#reachability~15 min

A missão

Problema

Um escape room tem n salas numeradas de 0 a n - 1. A sala 0 está aberta e todas as outras começam trancadas. Dentro da sala i há uma lista de chaves, rooms[i], e uma chave de número j abre a sala j. As chaves podem ser usadas quantas vezes você quiser e em qualquer ordem. Retorne True se você conseguir entrar em todas as salas. Há até 1.000 salas e até 3.000 chaves no total.

Exemplos

Input:  rooms = [[1], [2], [3], []]
Output: True
Por quê: a sala 0 tem a chave 1, a sala 1 tem a chave 2, a sala 2 tem a chave 3
Input:  rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: False
Por quê: a única chave da sala 2 está trancada dentro da própria sala 2
Input:  rooms = [[]]
Output: True
Por quê: edge case: a única sala já está aberta

Dicas

0 / 3

Tempo-alvo
O(n + k)
Espaço-alvo
O(n)

Restrições

  • n ≤ 1000 rooms
  • ≤ 3000 keys in total
  • room 0 starts open

Travou na ideia, e não no código? Busca em profundidade explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado