Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Easygraph-dfs

Flood Fill

Problem (yeniden ifade)

Bir görüntü ızgarası, başlangıç hücresi (sr, sc) ve yeni bir color verildiğinde, başlangıcı içeren 4-yön bağlantılı bileşeni (orijinal renkteki hücreler) boya ve görüntüyü döndür.

Sezgi

Başlangıç hücresi bir bileşeni tohumlar. Hâlâ orijinal renkte olan her 4-komşuyu ziyaret edip boya. Yeni renk orijinalle aynıysa hemen dön; yoksa sonsuz özyineleme.

Yaklaşımlar

Özyinelemeli DFS boyama

Doğrulanmadı

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

Fikir. orig = image[sr][sc]. orig === color ise dön. DFS: sınır dışı veya orig değil → dur; değilse boya ve dört yöne özyinele.

Yürüyüş. [[1,1,1],[1,1,0],[1,0,1]], start (1,1), color 2 → bağlı dört 1, 2 olur; köşedeki 1 yalnızca çapraz, kalır.

Trade-off. En kısa kod. Özyineleme derinliği bileşen boyutu; koca boyamalar yığını patlatabilir.

Çözüm

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) return;
    image[r]![c] = color;
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  dfs(sr, sc);
  return image;
}

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) return;
    image[r]![c] = color;
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  dfs(sr, sc);
  return image;
}

Yığın ile boyama

Doğrulanmadı

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

Fikir. Aynı boyama kuralı, açık yığın. Hücre çek, orig değilse atla, boya, dört komşuyu it.

Yürüyüş. Aynı ızgara, aynı sonuç. Yığın, bileşenin bekleyen sınırıdır.

Trade-off. Graph-DFS şablonuna uyar, çağrı yığını limitini aşmaz. Kuyruklu BFS aynı fikir; burada seviye sırası gerekmez.

Çözüm

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) continue;
    image[r]![c] = color;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) continue;
    image[r]![c] = color;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

Şablon bağlantısı

Graph DFS’in flood-fill şekli: hücreyi değiştir, 4-komşuya DFS/yığın. LC 695 aynı yürüyüş, renk yerine alan döndürür.

Yansıma

Başlangıç rengi hedefle aynıysa görüntüye dokunma. Değilse aynı renkteki 4 komşuyu boya.
Rengi değiştirmek işaret. Aynı renge boyamak sonsuz döngü; erken dönüş onu keser.
DFS veya yığın aynı bölgeyi boyar. Tek hücre. Sınır dışı yok.