İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarTekrarlarHakkında
Dil
EnglishTürkçe

Izgara ve Graf BFS

Rehber 3 / 6 · Yol 3 / 6

← ÖncekiSonraki →

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

Walls and Gates

Problem (yeniden ifade)

Izgara hücreleri: -1 duvar, 0 kapı, INF boş. Her boş odayı en yakın kapıya uzaklığa doldur (yerinde).

Sezgi

Tüm kapılardan aynı anda çok kaynaklı BFS; ilk dokunuş en kısadır.

Yaklaşımlar

Çok kaynaklı BFS

Tested only
Time O(m*n)Space O(m*n)

Fikir. Tüm 0’ları kuyruğa al; 4 yöne INF hücrelere genisle, dist+1 yaz.

Adım adım. Kapıya komşu odalar 1, sonra 2, … olur.

Trade-off’lar. Çok kaynaklı, her kapıdan ayrı BFS’ten üstündür.

Solution
export function wallsAndGates(rooms: number[][]): void {
  const m = rooms.length, n = rooms[0]?.length ?? 0;
  const q: [number, number][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (rooms[r]![c] === 0) q.push([r, c]);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (q.length) {
    const [r, c] = q.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr!, nc = c + dc!;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (rooms[nr]![nc] !== 2147483647) continue;
      rooms[nr]![nc] = rooms[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
}

export function wallsAndGates(rooms: number[][]): void {
  const m = rooms.length, n = rooms[0]?.length ?? 0;
  const q: [number, number][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (rooms[r]![c] === 0) q.push([r, c]);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (q.length) {
    const [r, c] = q.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr!, nc = c + dc!;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (rooms[nr]![nc] !== 2147483647) continue;
      rooms[nr]![nc] = rooms[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
}

Şablon bağlantısı

Izgara çok kaynaklı BFS.

Yansıma