Saltar al contenido

Abrir todas las habitaciones cerradas

Fácil#dfs#reachability~15 min

La misión

Problema

Un escape room tiene n habitaciones numeradas de 0 a n - 1. La habitación 0 está abierta y todas las demás empiezan cerradas con llave. Dentro de la habitación i hay una lista de llaves, rooms[i], y una llave con el número j abre la habitación j. Las llaves se pueden usar cualquier cantidad de veces y en cualquier orden. Devuelve True si puedes entrar a todas las habitaciones. Hay hasta 1000 habitaciones y hasta 3000 llaves en total.

Ejemplos

Input:  rooms = [[1], [2], [3], []]
Output: True
Por qué: la habitación 0 tiene la llave 1, la habitación 1 tiene la llave 2 y la habitación 2 tiene la llave 3
Input:  rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: False
Por qué: la única llave de la habitación 2 está encerrada dentro de la propia habitación 2
Input:  rooms = [[]]
Output: True
Por qué: caso límite: la única habitación ya está abierta

Pistas

0 / 3

Tiempo objetivo
O(n + k)
Espacio objetivo
O(n)

Restricciones

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

¿Lo que te frena es la idea y no el código? Búsqueda en profundidad lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio