Rotting Oranges

+10

Eşit uzunlukta satırlardan oluşan bir liste olarak bir ızgara verilir. Her hücre 0 (boş), 1 (taze bir portakal) veya 2 (çürük bir portakal) değerini alır. Her dakika, çürük bir portakalla yukarı, aşağı, sola veya sağa bitişik olan her taze portakal çürür. Hiç taze portakal kalmayana kadar geçen dakika sayısını döndür; bazı taze portakallar asla çürüyemiyorsa -1 döndür. Başlangıçta taze portakal içermeyen bir ızgara için 0 dakika gerekir.

Fonksiyon

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: ızgara, her satır için 0, 1 ve 2'den oluşan bir liste
Döndürürinteger: Hiçbir portakalın taze kalmasına kadar geçen dakika sayısı; bu hiç gerçekleşmezse -1

Kısıtlar

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Her satırın uzunluğu aynıdır.
Her grid[i][j] 0, 1 veya 2 değerini alır.

Örnekler

Girdi: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Çıktı: 6
Açıklama: Hücreleri (satır, sütun) şeklinde yazarak, çürüme (0,0) hücresinden başlar ve tek yolu izler: 1. dakikada (0,1), 2. dakikada (0,2) ve (1,1), 3. dakikada (2,1), 4. dakikada (2,0) ve (2,2), 5. dakikada (2,3). (1,3) hücresindeki portakal yalnızca (2,3) hücresine temas eder, bu yüzden en son, 6. dakikada çürür.

Gönderirken +21 gizli test

Ek soru

Çürümüş bir komşusu olduğunda her taze portakalın çürümesi için kendine özgü bir dakika sayısı gerektiğini varsayalım. Peki bitiş zamanını nasıl bulurdun?

Çözüm

Çürüme, tüm çürük portakallardan aynı anda başlar ve dakikada bir hücre ilerler; dolayısıyla yanıt bir mesafedir: en uzaktaki taze portakalın en yakın çürük portakala kaç adım uzakta olduğu. Başlamadan önce tüm çürük portakalları kuyruğa koyup kuyruğu her seferinde bir düzey, yani bir dakika işlemeniz koşuluyla, genişlik öncelikli arama bu mesafeyi tam olarak ölçer.

Dakika dakika simüle et

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Hikâyede anlatılanı yap. Her dakika, tüm ızgarayı tara ve çürük bir portakala dokunan tüm taze portakalları listele. Sonra hepsini çürüt, saate bir ekle ve yeniden tara. Taramada çürütecek hiçbir şey bulunmayana kadar durma. Bu noktada ızgarada hâlâ taze bir portakal varsa çürüme ona asla ulaşamaz: -1 döndür.

Önce listele, sonra çürüt. Tarama sırasında bir portakalı çürütürsen, aynı taramada daha sonra işlenen bir hücre onu çürük görür ve o da çürür; böylece çürüme bir dakikada birkaç hücre ilerler ve saat olduğundan düşük çıkar.

Bu doğru, ancak her dakika rows × cols hücrelik tam bir tarama gerektirir ve dakika sayısı hücre sayısına yaklaşabilir. Taze portakalların çürümenin başında bulunduğu, tek bir dolambaçlı yol oluşturduğu 150 × 150 boyutundaki bir ızgarada çürümenin ilerlemesi 11,324 dakika sürer: 22,500 hücrenin 11,324 kez taranması, yaklaşık 2.5 × 10^8 hücre kontrolü demektir; bunların neredeyse tamamı değişemeyen hücrelerde yapılır.

Algoritma

Dakikayı 0 olarak ayarla.
Izgarayı tara ve çürük bir komşusu olan her taze portakalı listele.
Liste boşsa dur. Aksi takdirde listedeki tüm portakalları çürüt, dakika değerine 1 ekle ve tekrar tara.
Taze portakal kalmışsa -1, yoksa dakika değerini döndür.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

Çok kaynaklı BFS'nin seviyelere göre uygulanması

Sezgi

Tarama, zamanını eylemin uzağındaki hücrelerde boşa harcar. t+1 dakikasında çürüyebilecek tek portakallar, t dakikasında çürüyen portakalların taze komşularıdır. Bu yüzden sırada yalnızca onları tut: çürümenin sınır kümesini.

Sırayı, 0. dakikada çürük olan tüm portakallarla başlat; hepsini birlikte ekle. Çok kaynaklı kısım budur. Taze bir portakal, en yakın çürük portakala olan uzaklığı kadar dakika sonra çürür ve tüm kaynaklarla başlatılan bir genişlik öncelikli arama, her hücreye ilk olarak hangi kaynak daha yakınsa onun üzerinden ulaşır. Tek bir arama, her kaynak için ayrı ayrı arama yapıp en küçüğünü bulma işini görür.

Ardından seviyeler halinde ilerle. Bir dakikanın başında sıra, geçen dakika çürüyen portakallardan oluşan k adet portakal içerir. Baştan tam olarak k tanesini al; her biri için taze komşularını çürütüp sıranın sonuna ekle. k tanesi tamamlandığında bir dakika geçmiş olur ve sıra bir sonraki sınır kümesini içerir. İlk örnekte seviyeler {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)} şeklindedir: başlangıçtan sonra altı adım, yani altı dakika.

Taze portakalları başlangıçta bir kez say ve her biri çürüdüğünde sayıyı azalt. Sayı 0'a ulaşır ulaşmaz dur; aksi hâlde son seviye, hiçbir şeyin çürümediği fazladan bir dakika ekler. Sayı 0'dan büyükken sıra boşalırsa -1 döndür. Her hücre sıraya en fazla bir kez girer ve dört komşusu kontrol edilir; bu yüzden işlem O(rows × cols) olur.

Algoritma

Çürük portakalların hepsini bir kuyruğa koy ve taze olanları say.
Dakikayı 0 olarak ayarla. Kuyruk boş değilken ve taze portakal kaldığı sürece dakikayı 1 artır ve kuyruğun boyutunu k olarak not et.
Önden k portakal al. Izgara içindeki her taze komşuyu çürük olarak işaretle, taze portakal sayısını azalt ve onu kuyruğun sonuna ekle.
Döngü sona erdiğinde, taze portakal sayısı 0 ise dakikayı, değilse -1 döndür.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Tuzaklar ve uç durumlar

Buradaki yanlış yanıtların çoğu bir dakika sapar ya da aramaya yanlış yerden başlamaktan kaynaklanır.

Son seviye için bir dakika saymak. Döngü kuyruk boşalana kadar çalışıyorsa son turunda hiçbir şeyi çürütmez ama yine de 1 ekler. Taze portakal kalmadığı anda dur.
Her çürük portakaldan sırayla arama yapmak. İlk arama, ulaştığı her portakalı kendi saatiyle sahiplenir; bu nedenle ortada buluşması gereken iki kaynak, olması gerekenden daha yüksek bir süre verir: [[2, 1, 1, 1, 1, 1, 1, 2]] 6 değil, 3 dakika sürer.
Dakika dakika sürümünde tarama sırasında portakalları çürütmek. Tarama sırasındaki daha sonraki bir hücre onları çürük olarak görür ve çürüme bir dakikada birkaç hücre boyunca yayılır.
Çürük portakal olmadığı için -1 döndürmek. Hiç taze portakal da yoksa yapılması gereken bir şey yoktur: [[0]] 0 döndürür. Yanıt yalnızca hiç çürümeyen taze portakallar varsa -1 olur.
Bir portakalı kuyruğa koyarken değil, kuyruktan çıkarırken çürük olarak işaretlemek. İki çürük portakalın yanındaki bir portakal kuyruğa iki kez girer ve taze portakal sayısı sıfırın altına düşer.
Derinlik öncelikli arama. Gidebildiği kadar derine tek bir yolu izler; bu yüzden bir portakala ilk ulaştığı an, o portakalın hangi dakikada çürüyeceği hakkında hiçbir şey söylemez.

Sıkça sorulan sorular4

Çürüyen Portakalların zaman karmaşıklığı nedir?

Genişlik öncelikli aramayla O(rows × cols). İlk tarama her hücreye bir kez bakar ve her turuncu en fazla bir kez kuyruğa girip dört komşuyu kontrol eder. En kötü durumda, çürük portakallarla dolu bir ızgarada kuyruk O(rows × cols) alan kaplar.

Çürüyen Portakallar için neden DFS değil de BFS kullanılır?

Genişlik öncelikli arama, hücreleri başlangıç noktasına olan uzaklıklarına göre ziyaret eder ve burada uzaklık zamanı ifade eder: Aramanın k düzeyi, tam olarak k. dakikada çürüyen portakallar kümesidir. Derinlik öncelikli arama, kısa yolu bulmadan önce uzun bir dolambaçlı yoldan bir hücreye ulaşabilir; bu nedenle daha kısa bir yol bulduğunda hücreleri her seferinde yeniden ziyaret etmesi gerekir.

Çok kaynaklı BFS nedir?

Kuyrukta bir hücre yerine, uzaklığı 0 olan birkaç hücreyle başlayan bir genişlik öncelikli arama. Tek bir geçişte her hücrenin en yakın kaynağa olan uzaklığını verir; bu, her kaynak için ayrı bir arama yapıp minimumu almakla elde edilen sonucun aynısıdır ve tek bir aramanın maliyetine sahiptir. Izgarada sorulan her türlü "en yakın X'e uzaklık" sorusu bunu kullanır.

Grid'i değiştirmeden Rotting Oranges problemini çözebilir misin?

Evet. Ayrı bir ziyaret edilmiş hücreler dizisi tutun ve ızgaraya 2 yazmak yerine bu diziyi kontrol edin. Bu, kuyruk zaten gerektirebileceği için O(rows × cols) ek bellek kullanır. Izgarayı referansla aktaran dillerde, ızgaraya yazmak çağıranın ızgarasını da değiştirir; görüşmeci size bunu sorabilir.

Python

def orangesRotting(grid):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

Beklenen