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 graph-dfs union-find

Number of Islands

Problem (yeniden ifade)

‘1’ (kara) ve ‘0’ (su) 2B ızgarasında ada sayısını döndür. Ada, en fazla 4-yön bağlı karadır.

Sezgi

Her ziyaret edilmemiş kara hücresi bir bileşen başlatır. Flood-fill (DFS/BFS) tüm adayı işaretler; fill’i kaç kez başlattığını say.

Yaklaşımlar

DFS flood fill

Doğrulanmadı

Zaman O(m·n)Alan O(m·n) worst-case stack

Fikir. Hücreleri dolaş; karada sayacı artır ve bağlı tüm karayı su/ziyaret edildi olarak işaretlemek için DFS.

Yürüyüş. İki ayrı kara lekesi olan ızgara → sayı 2.

Trade-off. DFS özlüdür; BFS açık kuyruk kullanır (dev ızgaralarda daha güvenli yığın derinliği).

Çözüm

export function numIslands(grid: string[][]): number {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0]!.length;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= m || c >= n || grid[r]![c] !== "1") return;
    grid[r]![c] = "0";
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  let count = 0;
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (grid[r]![c] === "1") { count++; dfs(r, c); }
  return count;
}

export function numIslands(grid: string[][]): number {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0]!.length;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= m || c >= n || grid[r]![c] !== "1") return;
    grid[r]![c] = "0";
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  let count = 0;
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (grid[r]![c] === "1") { count++; dfs(r, c); }
  return count;
}

Şablon bağlantısı

Izgara BFS/DFS bağlı bileşenler.

Yansıma

Kara 1 görününce sayacı artır, komşuları işaretle. İşaret yoksa aynı ada iki kez sayılır.
4 yön. Çapraz komşu ayrı ada. Köşe ve tek hücre.
Boş grid 0. Tüm su 0. Tüm kara 1.