Flood Fill

Recursos

Recursos
Fuente	Recurso	Notas
IUSACO	10.5 - Flood Fill	este módulo se basa en este capítulo
CP2	4.2.4 - Flood Fill	código + ejemplo

Video de YouTube (RspgKoZMing)

Introducción

Flood fill (relleno) es un algoritmo que identifica y etiqueta la componente conexa a la que pertenece una celda particular en un arreglo multidimensional.

Por ejemplo, supongamos que queremos partir la siguiente grilla en componentes de celdas conexas con el mismo número.

2	2	1
2	1	2
2	2	1

Empecemos el flood fill desde la celda superior izquierda. El esquema de colores será rojo para el nodo que se está procesando, azul para los nodos ya visitados, y sin color para los nodos todavía no visitados.

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

2	2	1
2	1	2
2	2	1

A diferencia de un grafo explícito, en el que se dan las aristas, una grilla es un grafo implícito. Eso significa que los vecinos son simplemente los nodos directamente adyacentes en las cuatro direcciones cardinales.

Por lo general, las grillas de los problemas son de $N$ por $M$ , así que la primera línea de la entrada contiene los números $N$ y $M$ . En este ejemplo usaremos un arreglo bidimensional de enteros para guardar la grilla, pero según el problema un arreglo bidimensional de caracteres o un arreglo bidimensional de booleanos puede ser más adecuado. Luego hay $N$ filas, cada una con $M$ números con el contenido de cada casilla de la grilla. Una entrada de ejemplo podría verse así (varía entre problemas):

Y vamos a leer la grilla de la siguiente forma:

C++JavaPython


#include <iostream>
 
using namespace std;
 
const int MAX_N = 1000;
 
int grid[MAX_N][MAX_N];
int row_num;
int col_num;
 
int main() {
	cin >> row_num >> col_num;
	for (int r = 0; r < row_num; r++) {
		for (int c = 0; c < col_num; c++) { cin >> grid[r][c]; }
	}
}


import java.io.*;
import java.util.StringTokenizer;
 
public class Floodfill {
	private static int[][] grid;
	private static int rowNum;
	private static int colNum;
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer dims = new StringTokenizer(read.readLine());
		rowNum = Integer.parseInt(dims.nextToken());
		colNum = Integer.parseInt(dims.nextToken());
		grid = new int[rowNum][colNum];
		for (int r = 0; r < rowNum; r++) {
			grid[r] = Arrays.stream(read.readLine().split(" "))
			              .mapToInt(Integer::parseInt)
			              .toArray();
		}
	}
}


row_num, col_num = [int(i) for i in input().split()]
grid = []
for _ in range(row_num):
	grid.append([int(i) for i in input().split()])

Implementación

Al hacer flood fill, vamos a mantener un arreglo de booleanos de $N\times M$ para saber qué casillas ya se visitaron, y una variable global para el tamaño de la componente actual que estamos visitando. Hay que guardar la grilla, el arreglo de visitados, las dimensiones y la variable de tamaño actual de forma global.

Esto significa que queremos llamar recursivamente a la función de búsqueda para las casillas de arriba, abajo, izquierda y derecha de la casilla actual. Por su naturaleza recursiva, flood fill se puede pensar como una versión modificada de DFS. El algoritmo para encontrar el tamaño de una componente conexa en una grilla usando flood fill es el siguiente (también mantendremos un arreglo 2D de visitados).

El código de abajo muestra las variables globales/estáticas que hay que mantener al hacer flood fill y el algoritmo de flood fill en sí:

C++JavaPython


const int MAX_N = 1000;
 
int grid[MAX_N][MAX_N];  // la grilla en sí
int row_num;
int col_num;
bool visited[MAX_N][MAX_N];  // indica qué nodos ya se visitaron
int curr_size = 0;           // se reinicia a 0 cada vez que empezamos una componente nueva
 
void floodfill(int r, int c, int color) {
	if ((r < 0 || r >= row_num || c < 0 || c >= col_num)  // si está fuera de rango
	    || grid[r][c] != color                            // color incorrecto
	    || visited[r][c]                                  // ya visitamos esta casilla
	)
		return;
 
	visited[r][c] = true;  // marcar la casilla actual como visitada
	curr_size++;           // incrementar el tamaño por cada casilla que visitamos
 
	// llamar flood fill de forma recursiva para las casillas vecinas
	floodfill(r, c + 1, color);
	floodfill(r, c - 1, color);
	floodfill(r - 1, c, color);
	floodfill(r + 1, c, color);
}
 
int main() {
	/*
	 * código de entrada y demás cosas específicas del problema
	 */
	for (int i = 0; i < row_num; i++) {
		for (int j = 0; j < col_num; j++) {
			if (!visited[i][j]) {
				curr_size = 0;
				/*
				 * empezar un flood fill si la casilla no se visitó todavía,
				 * y luego guardar o usar el tamaño de la componente
				 * para lo que se necesite
				 */
				floodfill(i, j, grid[i][j]);
			}
		}
	}
	return 0;
}


public class Floodfill {
	private static int[][] grid;  // la grilla en sí
	private static int rowNum;
	private static int colNum;           // dimensiones de la grilla, filas y columnas
	private static boolean[][] visited;  // indica qué nodos ya se
	                                     // visitaron
	private static int currSize = 0;  // se reinicia a 0 cada vez que empezamos una componente nueva
 
	public static void main(String[] args) {
		/*
		 * código de entrada y demás cosas específicas del problema
		 */
		for (int r = 0; r < rowNum; r++) {
			for (int c = 0; c < colNum; c++) {
				if (!visited[r][c]) {
					currSize = 0;
					/*
					 * empezar un flood fill si la casilla no se visitó
					 * todavía, y luego guardar o usar el tamaño de la
					 * componente para lo que se necesite
					 */
					floodfill(r, c, grid[r][c]);
				}
			}
		}
	}
 
	private static void floodfill(int r, int c, int color) {
		if ((r < 0 || r >= rowNum || c < 0 || c >= colNum)  // si está fuera de rango
		    || grid[r][c] != color                          // color incorrecto
		    || visited[r][c]  // ya visitamos esta casilla
		)
			return;
 
		visited[r][c] = true;  // marcar la casilla actual como visitada
		currSize++;            // incrementar el tamaño por cada casilla que visitamos
 
		// llamar flood fill de forma recursiva para las casillas vecinas
		floodfill(r, c + 1, color);
		floodfill(r, c - 1, color);
		floodfill(r - 1, c, color);
		floodfill(r + 1, c, color);
	}
}


import sys
 
MAX_N = 100
sys.setrecursionlimit(2**30)  # desactivar de hecho el límite de recursión
 
row_num = MAX_N
col_num = MAX_N
grid = [[0 for _ in range(col_num)] for _ in range(row_num)]
visited = [[False for _ in range(col_num)] for _ in range(row_num)]
curr_size = 0
 
 
def floodfill(r: int, c: int, color: int):
	global curr_size
 
	if (
		(r < 0 or r >= row_num or c < 0 or c >= col_num)  # si está fuera de rango
		or grid[r][c] != color  # color incorrecto
		or visited[r][c]  # ya visitamos esta casilla
	):
		return
 
	visited[r][c] = True  # marcar la casilla actual como visitada
	curr_size += 1  # incrementar el tamaño por cada casilla que visitamos
 
	# llamar flood fill de forma recursiva para las casillas vecinas
	floodfill(r, c + 1, color)
	floodfill(r, c - 1, color)
	floodfill(r - 1, c, color)
	floodfill(r + 1, c, color)
 
 
"""
código de entrada y demás cosas específicas del problema
"""
 
for r in range(row_num):
	for c in range(col_num):
		if not visited[r][c]:
			curr_size = 0
			"""
			empezar un flood fill si la casilla no se visitó todavía,
			y luego guardar o usar el tamaño de la componente
			para lo que se necesite
			"""
			floodfill(r, c, grid[r][c])

Ejemplo - Counting Rooms

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Counting Rooms	Fácil	Flood Fill	en el módulo

Implementación

Una implementación no recursiva de flood fill agrega los nodos adyacentes a una pila o cola, de forma similar a BFS, y suele implementarse así:

C++JavaPython


#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
const int MAX_N = 2500;
const int R_CHANGE[]{0, 1, 0, -1};
const int C_CHANGE[]{1, 0, -1, 0};
 
int row_num;
int col_num;
string building[MAX_N];
bool visited[MAX_N][MAX_N];
 
void floodfill(int r, int c) {
	// Nota: también se puede usar una cola y sacar del frente para un
	// enfoque basado en BFS
	stack<pair<int, int>> frontier;
	frontier.push({r, c});
	while (!frontier.empty()) {
		r = frontier.top().first;
		c = frontier.top().second;
		frontier.pop();
 
		if (r < 0 || r >= row_num || c < 0 || c >= col_num || building[r][c] == '#' ||
		    visited[r][c])
			continue;
 
		visited[r][c] = true;
		for (int i = 0; i < 4; i++) {
			frontier.push({r + R_CHANGE[i], c + C_CHANGE[i]});
		}
	}
}
 
int main() {
	cin >> row_num >> col_num;
	for (int i = 0; i < row_num; i++) { cin >> building[i]; }
 
	int room_num = 0;
	for (int i = 0; i < row_num; i++) {
		for (int j = 0; j < col_num; j++) {
			if (building[i][j] == '.' && !visited[i][j]) {
				floodfill(i, j);
				room_num++;
			}
		}
	}
	cout << room_num << endl;
}


import java.io.*;
import java.util.*;
 
public class RoomCount {
	public static final int R_CHANGE[] = {0, 1, 0, -1};
	public static final int C_CHANGE[] = {1, 0, -1, 0};
 
	private static boolean[][] visited;
	private static char[][] building;
	private static int rowNum;
	private static int colNum;
 
	public static void floodfill(int row, int col) {
		// Nota: también se puede usar una cola y sacar del frente para un
		// enfoque basado en BFS
		Stack<Pos> frontier = new Stack<>();
		frontier.push(new Pos(row, col));
		while (!frontier.isEmpty()) {
			Pos curr = frontier.pop();
			row = curr.row;
			col = curr.col;
 
			if (row < 0 || row >= rowNum || col < 0 || col >= colNum ||
			    building[row][col] == '#' || visited[row][col])
				continue;
 
			visited[row][col] = true;
			for (int i = 0; i < 4; i++) {
				frontier.add(new Pos(row + R_CHANGE[i], col + C_CHANGE[i]));
			}
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer dims = new StringTokenizer(read.readLine());
		rowNum = Integer.parseInt(dims.nextToken());
		colNum = Integer.parseInt(dims.nextToken());
 
		building = new char[rowNum][colNum];
		for (int r = 0; r < rowNum; r++) {
			String row = read.readLine();
			for (int j = 0; j < colNum; j++) { building[r][j] = row.charAt(j); }
		}
 
		visited = new boolean[rowNum][colNum];
		int roomNum = 0;
		for (int i = 0; i < rowNum; i++) {
			for (int j = 0; j < colNum; j++) {
				if (building[i][j] == '.' && !visited[i][j]) {
					floodfill(i, j);
					roomNum++;
				}
			}
		}
		System.out.println(roomNum);
	}
}
 
class Pos {
	int row;
	int col;
	public Pos(int row, int col) {
		this.row = row;
		this.col = col;
	}
}


row_num, col_num = [int(i) for i in input().split()]
grid = [input() for _ in range(row_num)]
visited = [[False for _ in range(col_num)] for _ in range(row_num)]
 
 
def floodfill(r: int, c: int):
	global visited
 
	"""
	Nota: también se puede usar una cola y sacar del
	frente (en lugar de sacar del final) para un enfoque basado en BFS
	"""
	frontier = [(r, c)]
	while frontier:
		r, c = frontier.pop()
		if (
			r < 0
			or r >= row_num
			or c < 0
			or c >= col_num
			or visited[r][c]
			or grid[r][c] == "#"
		):
			continue
 
		visited[r][c] = True
		frontier.append((r - 1, c))
		frontier.append((r, c - 1))
		frontier.append((r + 1, c))
		frontier.append((r, c + 1))
 
 
room_num = 0
for row in range(row_num):
	for col in range(col_num):
		if not visited[row][col] and grid[row][col] == ".":
			floodfill(row, col)
			room_num += 1
print(room_num)

Optimización en Python: padding

Podemos acelerar flood fill por un factor constante usando otra forma de evitar accesos fuera de rango a la grilla. Imaginemos un padding de una celda en los cuatro lados del arreglo, cuyas celdas están marcadas como ya visitadas. Así podemos eliminar la verificación de cotas en la que comprobamos si la siguiente celda que visitamos está entre 0 y las dimensiones del arreglo, inclusive. Esas celdas del padding pueden agregarse a la cola, pero cuando se visitan en el ciclo de flood fill se saltan por estar marcadas como visitadas y no ocurre ningún acceso fuera de rango. Además, no se agregan a la cola celdas fuera de rango más allá del padding.

Una opción para agregar padding sería empezar toda la grilla con una fila de relleno al comienzo, y también empezar cada fila con un elemento antes de leer la entrada. Después de la entrada, podemos agregar el padding al final de las filas y al fondo de la grilla. Sin embargo, en Python solo hace falta la segunda parte, porque el padding de la derecha y del fondo de la matriz puede actuar como padding de la izquierda y de arriba: la coordenada de la izquierda y de arriba, $-1$ , se interpreta como el final del arreglo.

El beneficio de velocidad de esta optimización solo se nota en algunas entradas grandes (incluso puede ser más lenta en entradas chicas) y probablemente solo conviene al usar un lenguaje lento como Python, donde incluso la solución esperada puede dar TLE. Nuestra nueva implementación del problema anterior sería la siguiente.


row_num, col_num = [int(i) for i in input().split()]
 
# Hacemos que cada fila sea una lista para poder hacer append al final.
grid = [[char for char in input()] for _ in range(row_num)]
visited = [[False for _ in range(col_num)] for _ in range(row_num)]
 
# Agregamos el padding acá
grid.append(["#"] * len(grid[0]))  # Agregar la fila de abajo
visited.append([True] * len(visited[0]))
for row_grid, row_visited in zip(grid, visited):  # Agregar el lado derecho
	row_grid.append("#")
	row_visited.append(True)
 
 
def floodfill(r: int, c: int):
	global visited
 
	frontier = [(r, c)]
	while frontier:
		r, c = frontier.pop()
 
		if visited[r][c] or grid[r][c] == "#":  # Sin verificación de cotas
			continue
 
		visited[r][c] = True
		frontier.append((r - 1, c))
		frontier.append((r, c - 1))
		frontier.append((r + 1, c))
		frontier.append((r, c + 1))
 
 
room_num = 0
for row in range(row_num):
	for col in range(col_num):
		if not visited[row][col] and grid[row][col] == ".":
			floodfill(row, col)
			room_num += 1
 
print(room_num)

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
Silver	★ Icy Perimeter	Fácil	Flood Fill	Solución
CF	Solve The Maze	Fácil	Flood Fill	Solución
Kattis	Map of Sweden	Fácil	Flood Fill, Connected Components	Solución
Old Silver	★ Cross Country Skiing	Fácil	Flood Fill, Binary Search	Solución
Silver	Switching on the Lights	Normal	Flood Fill	Solución
Silver	Build Gates	Normal	Flood Fill	Solución
Silver	Milk Pails	Normal	Flood Fill	Solución
Silver	★ Where's Bessie?	Normal	Flood Fill	Solución
Silver	★ Why Did the Cow Cross the Road III	Normal	Flood Fill	Solución
Silver	Mooyo Mooyo	Normal	Flood Fill	Solución
Silver	Comfortable Cows	Normal	Flood Fill	Solución
Silver	Snow Boots	Difícil	Flood Fill	Solución
Silver	2D Conveyor Belt	Difícil	Flood Fill	Solución
Silver	Maze Tac Toe	Difícil	Flood Fill	Solución
Silver	Multiplayer Moo	Difícil	Flood Fill	Solución