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.

🔗 Relacionados