Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumgrid-graph-bfs

Rotting Oranges

Problem (yeniden ifade)

Izgara hücreleri boş (0), taze portakal (1) veya çürük (2). Her dakika, bir çürüğe 4-yönde komşu olan her taze portakal çürür. Taze kalmayana kadar geçen dakikayı döndür; imkânsızsa -1.

Sezgi

Başlangıçta çürük tüm portakallar komşularını paralel bozar. Bu çok kaynaklı BFS’tir: kuyruğu zaman 0’da her çürük hücreyle doldur, sonra seviye seviye genişlet (her seviye = bir dakika).

Yaklaşımlar

Dakika bazlı çok kaynaklı BFS

Tested only

Time O(m·n)Space O(m·n)

Fikir. Taze portakalları say. Tüm çürük hücreleri kuyruğa al. Kuyruk boşalmayıp taze kaldıkça bir tam katmanı işle: komşu tazeleri çürüt, kuyruğa ekle, taze sayısını azalt. Her katman dakikayı artırır.

Adım adım. [[2,1,1],[1,1,0],[0,1,1]] → tüm tazeler 4 dakikada çürür.

Trade-off’lar. Her çürükten tek kaynaklı BFS alıp min süreleri almak daha yavaş ve dağınık. Yerinde mutasyon hücreleri çürük işaretler; yeniden kuyruğa alınmazlar.

Solution

export function orangesRotting(grid: number[][]): number {
  const R = grid.length;
  const C = grid[0]?.length ?? 0;
  const q: [number, number][] = [];
  let fresh = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r]![c] === 2) q.push([r, c]);
      else if (grid[r]![c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let minutes = 0;
  let head = 0;
  while (head < q.length && fresh > 0) {
    const size = q.length - head;
    for (let s = 0; s < size; s++) {
      const [r, c] = q[head++]!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (grid[nr]![nc] !== 1) continue;
        grid[nr]![nc] = 2;
        fresh--;
        q.push([nr, nc]);
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

export function orangesRotting(grid: number[][]): number {
  const R = grid.length;
  const C = grid[0]?.length ?? 0;
  const q: [number, number][] = [];
  let fresh = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r]![c] === 2) q.push([r, c]);
      else if (grid[r]![c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let minutes = 0;
  let head = 0;
  while (head < q.length && fresh > 0) {
    const size = q.length - head;
    for (let s = 0; s < size; s++) {
      const [r, c] = q[head++]!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (grid[nr]![nc] !== 1) continue;
        grid[nr]![nc] = 2;
        fresh--;
        q.push([nr, nc]);
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Şablon bağlantısı

Bayrak taşıyıcı çok kaynaklı ızgara BFS. 01 Matrix (542) ve walls-and-gates tarzı problemlerle aynı iskelet.

Yansıma

Hangi kalıp bunu 90 saniyede ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?