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

01 Matrix

Problem (yeniden ifade)

İkili bir matris verildiğinde, her hücrenin en yakın 0’a uzaklığını tutan aynı boyutta bir matris döndür (4-yönlü). Uzaklık, komşu bir hücreye adım sayısıdır.

Sezgi

En yakın sıfıra uzaklık, ağırlıksız ızgarada en kısa yoldur. Her 1’den BFS yerine tüm sıfırlardan birden başla (çok kaynaklı) ki her hücre bir kez yerleşsin.

Yaklaşımlar

Tüm sıfırlardan çok kaynaklı BFS

Doğrulanmadı

Zaman O(m·n)Alan O(m·n)

Fikir. Her 0’ı uzaklık 0 ile kuyruğa al. 4-komşuya genişlet; bir komşu katı daha küçük uzaklık alırsa güncelle ve kuyruğa ekle. Ağırlıksız grafarda ilk ziyaret optimaldir.

Yürüyüş. [[0,0,0],[0,1,0],[1,1,1]] → uzaklıklar [[0,0,0],[0,1,0],[1,2,1]].

Trade-off. İki geçişli DP (önce sol-üst sonra sağ-alt) da O(m·n)’de, daha az kuyruk belleğiyle çalışır. Çok kaynaklı BFS kalıba hizalı zihinsel modeldir.

Çözüm

export function updateMatrix(mat: number[][]): number[][] {
  const R = mat.length;
  const C = mat[0]!.length;
  const dist = Array.from({ length: R }, () => new Array<number>(C).fill(Infinity));
  const q: [number, number][] = [];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (mat[r]![c] === 0) {
        dist[r]![c] = 0;
        q.push([r, c]);
      }
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let head = 0;
  while (head < q.length) {
    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 (dist[nr]![nc]! <= dist[r]![c]! + 1) continue;
      dist[nr]![nc] = dist[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
  return dist;
}

export function updateMatrix(mat: number[][]): number[][] {
  const R = mat.length;
  const C = mat[0]!.length;
  const dist = Array.from({ length: R }, () => new Array<number>(C).fill(Infinity));
  const q: [number, number][] = [];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (mat[r]![c] === 0) {
        dist[r]![c] = 0;
        q.push([r, c]);
      }
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let head = 0;
  while (head < q.length) {
    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 (dist[nr]![nc]! <= dist[r]![c]! + 1) continue;
      dist[nr]![nc] = dist[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
  return dist;
}

Şablon bağlantısı

Rotting Oranges (994) ile aynı çok kaynaklı BFS: tüm kaynakları uzaklık 0’da tohumla, dışa genişlet.

Yansıma

Tüm 0’lar kaynak, mesafe 0. Her hücre bir kez. Tek kaynaklı arama her 1 için O(mn²).
İlk ulaşan en kısa mesafedir. 1’i tekrar kuyruğa alırsan katmanlar şişer.
Hepsi 0. Köşedeki tek 1. Duvar yok; her hücre geçilir.