DEV//UNIT
← АлгоритмыGraphs

Заливка (Flood Fill)

Закрасить связную область: волна от точки, стены не перепрыгнуть.

время O(клеток области)память O(клеток)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function floodFill(
2  map: string[],
3  visited: boolean[][],
4  row: number,
5  col: number,
6): number {
7  const stack: Array<[number, number]> = [[row, col]]
8  let filled = 0
9 
10  while (stack.length > 0) {
11    const [r, c] = stack.pop() as [number, number]
12    if (r < 0 || r >= map.length) continue
13    if (c < 0 || c >= map[0].length) continue
14    if (map[r][c] === '#' || visited[r][c]) continue
15 
16    visited[r][c] = true
17    filled++
18 
19    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1])
20  }
21 
22  return filled
23}

Проблема

Инструмент «ведро» в Paint: перекрасить связную область. Рекурсивный обход без защиты от повторов зацикливается на первой же петле из соседних пикселей.

Что вы видите

Сетка-лабиринт: заливка расходится от старта, заливая всё достижимое.

Как это работает

BFS/DFS по клеткам: стек соседей, посещённые не повторяем. Каждый пиксель области входит в стек ровно один раз — линейность. Так работает инструмент «ведро» в Paint и подсчёт областей на картах.

Пошаговый разбор

  1. 01

    Старт

    Клетка-источник и её соседи.

  2. 02

    Волна

    Соседи соседей — пока не стены.

  3. 03

    Финал

    Залита вся связная область.

Complexity и ограничения

time
O(клеток области)
space
O(клеток)

См. complexity в шапке страницы.

Edge cases

  • Вся область одного цвета со стартом того же цвета

    Зальётся всё изображение — граница только края канвы.

  • Замкнутая стена вокруг старта

    Волна упирается и гаснет — заливается только внутренность.

  • Старт на стене (#)

    Первый же чек отклоняет — ноль залитых.

Где встречается в реальности

Продукт

Классический приём в реальных системах.

Собеседования

Стандартный вопрос на понимание структуры.

Связанные алгоритмы

Поиск в ширину (BFS)Поиск в глубину (DFS)
Shorts

«Как работает «ведро» в Paint»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Как работает «ведро» в Paint
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/flood-fill