Çürüyen portakallar

Problem

Bir kasadaki portakallar ızgara olarak veriliyor: 0 boş hücre, 1 taze portakal, 2 çürük portakal. Her dakika, çürük bir portakalın dört yönlü komşusu olan taze portakallar çürür. Tüm taze portakalların çürümesi için geçmesi gereken en az dakikayı döndür. Bir taze portakal hiçbir zaman çürüyemiyorsa -1 döndür.

2 1 0
0 1 1
0 0 1

Çıktı: 4
dakika 1: (0,1)   dakika 2: (1,1)   dakika 3: (1,2)   dakika 4: (2,2)

2 1 1 1 2

Çıktı: 2   (iki uçtan aynı anda yayılıp ortada buluşuyor)

2 0 1   -> -1   (boş hücre yayılımı kesiyor)
0 2     ->  0   (çürütülecek taze portakal yok)

Netleştirme soruları

• Başlangıçta hiç taze portakal yoksa cevap 0 mı? (Evet; çürük portakal olmasa bile.)
• Taze portakal var ama hiç çürük yoksa? (-1.)
• Yayılma 4 yönlü mü? (Evet.)
• Girdiyi değiştirebilir miyim?
• Izgara boyutu? (LeetCode'da 10x10'a kadar küçük, ama çözüm genel olmalı.)

İpuçları

Yaklaşım

Simülasyon (kaba çözüm): Her dakika tüm ızgarayı tara, çürük komşusu olan tazeleri işaretle, değişiklik olmayana kadar tekrarla. Her tur O(m·n) ve tur sayısı en fazla O(m·n) olabilir (yılan şeklinde bir yol); toplam O((m·n)²).

Her çürükten ayrı BFS: Her taze portakal için tüm çürüklere olan minimum mesafeyi hesaplar; k çürük için O(k·m·n).

Çok kaynaklı BFS (optimal): Tüm çürük portakalları 0. dakikada kuyruğa koy. BFS katman katman ilerlediğinde, her taze portakala en yakın çürükten gelen dalga ilk ulaşır; çünkü tüm kaynaklar aynı anda başladı. Bu, grafa tüm çürüklere 0 ağırlıklı kenarla bağlı sanal bir "süper kaynak" eklemekle eşdeğerdir. Cevap, son taze portakalın çürüdüğü katman numarasıdır.

Sayaç ayrıntısı: Dakikayı her katmandan sonra artırırsan, son katman işlendikten sonra (artık yeni çürüyen yokken) bir fazla sayarsın. Döngü koşuluna fresh > 0 eklemek bunu temizce çözer: son taze portakal çürüdüğü anda döngü biter.

Java çözümü

import java.util.ArrayDeque;

public final class RottingOranges {

    private static final int EMPTY = 0, FRESH = 1, ROTTEN = 2;
    private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] state = new int[rows][];
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        for (int r = 0; r < rows; r++) {
            state[r] = grid[r].clone();                  // girdiyi bozmamak için kopya
            for (int c = 0; c < cols; c++) {
                if (state[r][c] == ROTTEN) queue.offer(new int[]{r, c});   // çok kaynaklı BFS: hepsi 0. dakikada
                else if (state[r][c] == FRESH) fresh++;
            }
        }

        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {          // fresh > 0: son katmandan sonra boşuna dakika sayma
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] cell = queue.poll();
                for (int[] d : DIRECTIONS) {
                    int r = cell[0] + d[0], c = cell[1] + d[1];
                    if (r >= 0 && r < rows && c >= 0 && c < cols && state[r][c] == FRESH) {
                        state[r][c] = ROTTEN;
                        fresh--;
                        queue.offer(new int[]{r, c});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

Girdi kopyalanıyor, çünkü çözüm hücre durumlarını değiştiriyor; mülakatta girdiyi değiştirmeye izin alındıysa kopya kaldırılabilir. Durumlar için sabitler (FRESH, ROTTEN) sihirli sayıları ortadan kaldırır.

Karmaşıklık

• Zaman: O(m·n). Her hücre en fazla bir kez kuyruğa girer, her birinin 4 komşusu kontrol edilir.
• Bellek: O(m·n) kopya ızgara ve en kötü durumda O(m·n) kuyruk (başlangıçta tüm hücreler çürükse).

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Örnek: 4 dakika.
• İki uçtan yayılma (2 1 1 1 2): 2 dakika.
• Boş hücreyle ayrılmış taze portakal: -1.
• Hiç taze yok (0 2): 0; sadece boş hücre: 0.
• Taze var, çürük yok (1): -1.
• Girdi değişmemiş.
• 2.000 rastgele ızgara (1-6 boyut), dakika dakika simülasyon referansıyla karşılaştırıldı.

Dakika sayacındaki off-by-one hatası en sık hatadır; "hiç taze yok" ve "tek adımda biter" testleri bunu hemen yakalar.

Mülakatçı için

Bu soru, adayın BFS'in "en kısa mesafe" özelliğini anlayıp anlamadığını ve çok kaynaklı BFS fikrine ulaşıp ulaşamadığını ölçer. Her çürük için ayrı BFS başlatan aday çalışan bir çözüm üretir ama zaman tahmini yanlış olur; bunu karmaşıklık sorusuyla açığa çıkar.

Gözlemle: dakika sayacının nerede artırıldığı, -1 koşulunun nasıl tespit edildiği (taze sayacı ya da sonda tekrar tarama; ikisi de kabul edilebilir), hiç taze olmayan durumun 0 dönmesi.

İpucu zamanlaması: Aday simülasyonla başlarsa bitirmesine izin ver, sonra karmaşıklığı sor ve ilk ipucunu ver. Ayrı BFS'lere yönelirse ikinci ipucunu hemen kullanabilirsin; çok kaynaklı BFS fikri bu sorunun öğretmek istediği şeydir.

Takip sorusu 1: Bazı hücreler "yavaş" ve çürüme oraya 2 dakikada geçiyor. Beklenen: kenar ağırlıkları artık farklı; BFS yetmez. Ağırlıklar 1 ve 2 ise 0-1 BFS benzeri bir deque hilesi ya da genel durumda Dijkstra.

Takip sorusu 2: Her boş hücreye en yakın kapıya olan mesafeyi yaz (Walls and Gates). Beklenen: aynı çok kaynaklı BFS; kaynaklar kapılar (LeetCode 286).

Takip sorusu 3: Bunun gerçek hayattaki karşılığı ne olabilir? Beklenen: bir mikroservis grafında bir arızanın (ya da bir config değişikliğinin) yayılma süresi, ağda bir mesajın tüm düğümlere ulaşma süresi; çok kaynaklı BFS'in "aynı anda başlayan olaylar" modellemesi.

Benzer problemler

• Walls and Gates (LeetCode 286)
• 01 Matrix (LeetCode 542)
• As Far from Land as Possible (LeetCode 1162)
• Shortest Path in Binary Matrix (LeetCode 1091)
• Number of Islands (LeetCode 200)