İçeriğe geç

Kilitli her odayı aç

Kolay#dfs#reachability~15 dk

Görev tanımı

Problem

Bir kaçış odasında 0'dan n - 1'e kadar numaralanmış n oda var. 0 numaralı oda açık, diğer her oda kilitli başlıyor. i numaralı odanın içinde bir anahtar listesi, rooms[i], duruyor; j numaralı bir anahtar j numaralı odayı açıyor. Anahtarlar istenen sayıda ve istenen sırada kullanılabilir. Her odaya girebiliyorsan True döndür. En fazla 1.000 oda ve toplamda en fazla 3.000 anahtar var.

Örnekler

Input:  rooms = [[1], [2], [3], []]
Output: True
Neden: 0 numaralı oda 1 numaralı anahtarı, 1 numaralı oda 2 numaralı anahtarı, 2 numaralı oda 3 numaralı anahtarı tutuyor
Input:  rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: False
Neden: 2 numaralı odanın tek anahtarı bu odanın kendi içinde kilitli
Input:  rooms = [[]]
Output: True
Neden: edge case: tek oda zaten açık

İpuçları

0 / 3

Hedef zaman
O(n + k)
Hedef alan
O(n)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? Derinlik öncelikli arama bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case