Mediumgraph-dfs
Max Area of Island
Problem (yeniden ifade)
0 (su) ve 1 (kara) ızgarasında bir ada, 4-yön bağlı 1’ler grubudur. En büyük adanın alanını döndür; kara yoksa 0.
Sezgi
LC 200, flood fill’i kaç kez başlattığını sayar. Burada her fill boyadığı hücre sayısını döndürür. Maksimumu tut.
Yaklaşımlar
DFS alan
DoğrulanmadıZaman O(m·n)Alan O(m·n) worst-case stack
Fikir. Karada DFS, 1 + dört özyinelemeli çağrı döndürür; hücreyi 0 yaparak tekrar sayılmaz. Izgarayı tara; best = max(best, dfs(r, c)).
Yürüyüş. Boyut 1 ve 3 olan iki ada → 3. Hep su → 0.
Trade-off. Izgarayı mutasyona uğratmak yığın dışında O(1) ek alan. Mutasyon yasaksa visited matrisi aynı iş. Her hücre bir kez girilir, zaman ızgarayla doğrusal.
Çözüm
export function maxAreaOfIsland(grid: number[][]): number {
if (!grid.length) return 0;
const m = grid.length, n = grid[0]!.length;
const dfs = (r: number, c: number): number => {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r]![c] === 0) return 0;
grid[r]![c] = 0;
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
};
let best = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (grid[r]![c] === 1) best = Math.max(best, dfs(r, c));
return best;
}
export function maxAreaOfIsland(grid: number[][]): number {
if (!grid.length) return 0;
const m = grid.length, n = grid[0]!.length;
const dfs = (r: number, c: number): number => {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r]![c] === 0) return 0;
grid[r]![c] = 0;
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
};
let best = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (grid[r]![c] === 1) best = Math.max(best, dfs(r, c));
return best;
}
Şablon bağlantısı
Graph DFS’in flood-fill şekli; DFS void yerine sayım döndürür. LC 733 / LC 200 ile aynı iskelet.
Yansıma
- Kara 1 görününce alanı say ve işaretle. Cevap en büyük işaretli bileşen. 4 yön.
- İşaret yoksa aynı ada iki kez sayılır. Çapraz komşu ayrı ada.
- Ada yok 0. Tek hücre 1. Tüm kara
m*n.