Kalıp #14
Izgara ve Graf BFS
TemelAğırlıksız graflarda en kısa yollar ve ızgarada çok kaynaklı seller.
Ne zaman kullanılır
Her kenar maliyeti aynı (veya her ızgara adımı bir hamle). Mesafe, erişilebilirlik veya flood fill ile bağlı bileşenler lazım.
Tanıma ipuçları
- Izgarada / word ladder en kısa yol
- Ada sayısı / çürüyen portakallar
- Tüm kapılardan veya çürüyen hücrelerden çok kaynaklı BFS
Yaygın tuzaklar
- Kuyruğa koyarken ziyaret işaretlememek (yinelenenler patlar)
- Problemle 4 yön vs 8 yön tutarsızlığı
- En kısa yol gerekirken DFS kullanmak
90 saniyelik tanıma egzersizi
Hangisi en iyi uyuyor?
- Izgarada / word ladder en kısa yol
- Ada sayısı / çürüyen portakallar
- Tüm kapılardan veya çürüyen hücrelerden çok kaynaklı BFS
Interactive
Zihinsel model
Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.
queue = [S] · dist[S] = 0
Grid BFS: treat each cell as a node; 4-neighbors are edges. Seed the queue at the start.
Nasıl düşünülür
BFS seviye seviye keşfeder. Zihinsel model ızgara ve serbest grafları (komşuluk) çizer; düğüm, kenar ve mesafeleri görürsün. Bir düğüme ilk varış en az kenar sayısıdır. Izgarada komşular yukarı/aşağı/sol/sağ. Çok kaynaklı BFS kuyruğu tüm başlangıçlarla mesafe 0’da tohumlar.
Şablon şekilleri
| Şekil | Temel hamle | Notlar |
|---|---|---|
| Tek kaynak | Kuyruk + dist map | İlk varış kazanır |
| Çok kaynak | Tüm kaynakları kuyruğa | Aynı genişleme |
| Bileşenler | Ziyaret edilmemiş her birini flood | Ada say |
Karmaşıklık temeli
O(V+E) (ızgarada O(R·C)). Kuyruk ve ziyaret için O(V) alan.
Şablondan probleme
- Komşuları ve geçerli hücre predikatını tanımla.
- Kaynak(lar)dan kuyruk ve visited (veya dist) başlat.
- While queue: pop, kullanılmamış komşuları genişlet, dist kaydet.
- Hedef bulunduysa erken dur; yoksa sayım/mesafe döndür.
Şablon
TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.
/** Grid BFS template: multi-source flood from all zeros (dist fill). */
export function wallsAndGatesTemplate(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]] as const;
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]);
}
}
}
/** Grid BFS template: multi-source flood from all zeros (dist fill). */
export function wallsAndGatesTemplate(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]] as const;
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]);
}
}
}
- 1#127 Word LadderRehberhard
- 2#200 Number of IslandsRehbermedium
- 3#286 Walls and GatesRehbermedium
- 4#542 01 MatrixRehbermedium
- 5#752 Open the LockRehbermedium
- 6#994 Rotting OrangesRehbermedium