Záplavové vyplnění

O(cells)

Záplavové vyplnění obarví propojenou oblast: z jedné buňky se rozšíří do každého volného 4-sousedního souseda a dál do jejich sousedů, přičemž se zastaví jen u zdí a okraje mřížky. Je to přesně prohledávání do šířky bez cíle — pokračuje, dokud není celá dosažitelná oblast vyplněna. Stejný princip pohání nástroj plechovky barvy, odkrývání prázdných ploch v Minesweeperu i počítání propojených oblastí v obrázku. Každou buňku navštíví jednou, takže běží v čase lineárním k počtu buněk. (Verze do hloubky či rekurzivní vyplní stejnou oblast v jiném pořadí.)

Klikni na buňku pro přepnutí zdi
Mřížka
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni v zárodečné buňce a označ ji k vyplnění.
  2. Rozšiř se do každého volného souseda, který ještě nebyl viděn.
  3. Pokračuj ven, nikdy nepřekroč zeď ani okraj.
  4. Zastav se, až je celá propojená oblast vyplněna.

Pseudokód

1floodFill(grid, start):              # O(cells)2  queue ← [start]; seen ← {start}3  while queue not empty:4    cell ← queue.dequeue()5    fill cell6    for nbr in open neighbours(cell):7      if nbr not seen:8        seen.add(nbr); queue.enqueue(nbr)9  # the whole connected region is filled