Flood fill
Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 15 de la Ruta de Aprendizaje.
Qué hace
Pinta toda la región conectada a una celda de una grilla. Es un DFS (o BFS) donde los vecinos son las celdas de arriba, abajo, izquierda y derecha en vez de una lista de adyacencia.
Complejidad: O(filas × columnas): cada celda se visita una vez.
Cuándo usarlo
Contar islas, habitaciones o regiones; medir el tamaño de una zona; cualquier problema de grilla que hable de ‘conectado’. La idea clave es que una grilla es un grafo disfrazado. Módulo 15 de la Ruta de Aprendizaje.
Implementación recomendada (C++)
int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1}; // abajo, arriba, derecha, izquierda
void inundar(vector<string>& m, int i, int j, char libre) {
if (i < 0 || i >= (int)m.size() || j < 0 || j >= (int)m[0].size()) return; // fuera
if (m[i][j] != libre) return; // muro, o ya pintada
m[i][j] = 'x'; // pintar = marcar visitada
for (int d = 0; d < 4; d++) inundar(m, i + dx[d], j + dy[d], libre);
}
// contar regiones: lanzar una inundación por cada celda libre que quede
// (m se recibe por valor a propósito: se pinta la copia, el mapa original queda intacto)
int regiones(vector<string> m) {
int c = 0;
for (int i = 0; i < (int)m.size(); i++)
for (int j = 0; j < (int)m[0].size(); j++)
if (m[i][j] == '.') { c++; inundar(m, i, j, '.'); }
return c;
}⚠️ Notas
El chequeo de bordes va primero, antes de mirar el contenido de la celda. En grillas de 1000×1000 (10^6 celdas) la versión recursiva roza el límite de la pila: si el juez da RTE, pásala a BFS con cola. Con 8 vecinos (diagonales incluidas), amplía dx/dy a 8 entradas.