Flood Fill

Q: ¿Cuál es la complejidad temporal de Flood Fill?

O(m × n) para una imagen con m filas y n columnas. Cada píxel de la región se apila una vez y examina cuatro vecinos, y los píxeles fuera de la región solo se examinan como vecinos. La pila puede contener hasta m × n píxeles cuando toda la imagen es una sola región.

Q: ¿Deberías usar BFS o DFS para el relleno por inundación?

Ambos funcionan y tienen un tiempo de ejecución O(m × n). La región es la misma, independientemente del orden en que la recorras, así que una cola (búsqueda en anchura) y una pila (búsqueda en profundidad) pintan los mismos píxeles. Elige la opción que sea más breve de escribir en tu lenguaje y evita la recursión en imágenes grandes.

Q: ¿Por qué Flood Fill entra en un bucle infinito cuando el nuevo color es igual al anterior?

La solución habitual interpreta «sigue teniendo el color antiguo» como «todavía no se ha visitado». Cuando el nuevo color es igual al antiguo, pintar un píxel no lo cambia, así que sus píxeles vecinos lo vuelven a añadir a la pila y la búsqueda nunca termina. Comprobar primero este caso y devolver la imagen lo soluciona, y la imagen sin cambios es la respuesta correcta.

Q: ¿Se puede resolver Flood Fill de forma recursiva?

Sí, una función que pinta un píxel y se llama a sí misma para cada vecino del color antiguo es correcta. El riesgo está en la profundidad: la recursión alcanza una profundidad igual a la del camino más largo que sigue la búsqueda, que en una región sinuosa puede llegar a miles de llamadas. Una pila explícita realiza el mismo trabajo sin ese límite.

FácilGrafos

+10

Una imagen es una cuadrícula de números enteros, donde cada número representa el color de un píxel. Recibes la imagen como una lista de filas, un píxel inicial en la fila sr y la columna sc, y un nuevo color. Vuelve a pintar la región que contiene el píxel inicial: cada píxel del mismo color que el píxel inicial al que puedes llegar desde este avanzando hacia arriba, abajo, izquierda o derecha a través de píxeles de ese mismo color. Devuelve la imagen después de volver a pintarla.

Función

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: la imagen como una lista de filas, un número por píxel
srinteger: la fila del píxel inicial, contada desde 0
scinteger: la columna del píxel inicial, contada desde 0
colorinteger: el nuevo color de la región
Devuelveinteger-2d-array: la imagen después de que se vuelva a dibujar la región

Restricciones

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Cada fila tiene la misma longitud.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length y 0 ≤ sc < image[0].length

Ejemplos

Entrada: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Salida: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Explicación: La casilla inicial contiene el color 1. El 1 a su derecha, los 1 de la columna izquierda y de la fila inferior, y el 1 encima de la esquina inferior derecha están conectados a ella, así que los siete pasan a ser 5. Los dos 0 son de otro color y lo conservan.

+18 pruebas ocultas al enviar

Para ir más allá

¿Cómo cambiaría tu solución si los píxeles que solo se tocan en una esquina también se consideraran conectados?

Solución

La región es una parte conexa de un grafo: los píxeles son nodos, y dos píxeles del color inicial que comparten un lado están conectados. Cualquier búsqueda que comience en el píxel dado y avance solo a través de ese color encuentra toda la región. Las dos trampas son una imagen en la que el color nuevo es igual al antiguo y una región larga y sinuosa que hace fallar una búsqueda recursiva.

Búsqueda en profundidad recursiva

Correcto, pero no termina con las pruebas más grandes

Intuición

Escribe una función paint(r, c) que haga una cosa pequeña: si (r, c) está dentro de la imagen y todavía tiene el color antiguo, asígnale el nuevo color y llámate a sí misma en los cuatro vecinos. Una llamada en el píxel inicial se propaga por toda la región, porque cada píxel de la región está conectado al inicio por un camino de píxeles del color antiguo, y las llamadas siguen ese camino.

Pintar el píxel antes de las cuatro llamadas es lo que evita que la propagación dé vueltas en círculos: cuando un vecino vuelve a llamar a un píxel ya pintado, el color ya no coincide y la llamada termina de inmediato. Esto solo funciona cuando el nuevo color es distinto del antiguo, así que compruébalo primero y devuelve la imagen sin cambios cuando sean iguales.

El trabajo es O(m × n), pero la pila de llamadas es el punto débil. La recursión alcanza la profundidad del camino que está siguiendo. Una serpiente de un píxel de ancho que recorra una imagen de 80 × 80 tiene unos 3.200 píxeles de longitud, así que las llamadas se anidan unas 3.200 veces. Python se detiene en 1.000 de forma predeterminada y genera un error, por lo que este enfoque no termina en las pruebas más grandes. Otros lenguajes permiten llamadas más profundas, pero una imagen más grande también agotaría su pila de llamadas.

Algoritmo

Lee old = image[sr][sc]. Si old es igual a color, devuelve la imagen.
Define paint(r, c): devuelve el resultado si (r, c) está fuera de la imagen o su color no es old.
De lo contrario, establece image[r][c] = color y llama a paint para los píxeles de arriba, abajo, izquierda y derecha.
Llama a paint(sr, sc) y devuelve la imagen.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

Búsqueda en profundidad con una pila explícita

Intuición

Haz el mismo recorrido, pero mantén los píxeles que quedan por visitar en una pila propia en lugar de en la pila de llamadas. Pinta el píxel inicial y apílalo. Desapila un píxel, examina sus cuatro vecinos y, por cada vecino que esté dentro de la imagen y aún tenga el color antiguo, píntalo y apílalo. Cuando la pila esté vacía, habrás pintado toda la región.

Pinta un píxel cuando lo apiles, no cuando lo desapiles. Un píxel pintado ya no tiene el color antiguo, así que la comprobación del color también sirve para comprobar si ya se visitó: ningún píxel entra dos veces en la pila y no necesitas una cuadrícula aparte de marcas. Al igual que en la versión recursiva, esto requiere que el color nuevo sea distinto del antiguo, así que devuelve la imagen sin cambios cuando sean iguales.

Cada píxel de la región se apila una vez y se comprueban sus cuatro vecinos, así que el tiempo es O(m × n). La pila contiene como máximo los píxeles de la región. Se almacena en la memoria ordinaria, así que una región sinuosa de 3,200 píxeles no es un problema, mientras que la versión recursiva agotaba la pila de llamadas.

Algoritmo

Lee old = image[sr][sc]. Si old es igual a color, devuelve la imagen.
Pinta (sr, sc) y añádelo a una pila.
Extrae un píxel de la pila y observa sus cuatro vecinos.
Para cada vecino dentro de la imagen cuyo color sea old, píntalo y añádelo a la pila.
Cuando la pila esté vacía, devuelve la imagen.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben al mismo caso de color, a salir de la imagen o a la recursión en una región larga.

Olvidar el caso en que color es igual al color inicial. Pintar después no cambia nada, así que una búsqueda que usa el color como marca de visitado añade los mismos píxeles sin parar.
Leer image[sr][sc] después de pintarlo. Guarda primero el color antiguo o compararás cada vecino con el nuevo color.
Contar los vecinos diagonales. Los píxeles que solo se tocan en una esquina no están conectados.
Comprobar el color de un vecino antes de verificar que está dentro de la imagen. Comprueba primero 0 ≤ row < rows y 0 ≤ col < cols.
Usar recursión en una imagen grande. Un recorrido de un píxel de ancho a través de una imagen de 80 × 80 tiene unos 3,200 píxeles de longitud, suficiente para superar el límite de recursión de Python.
Pintar todos los píxeles del color antiguo de toda la imagen. Los píxeles de ese color que estén aislados del punto inicial deben conservar su color.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Flood Fill?

O(m × n) para una imagen con m filas y n columnas. Cada píxel de la región se apila una vez y examina cuatro vecinos, y los píxeles fuera de la región solo se examinan como vecinos. La pila puede contener hasta m × n píxeles cuando toda la imagen es una sola región.

¿Deberías usar BFS o DFS para el relleno por inundación?

Ambos funcionan y tienen un tiempo de ejecución O(m × n). La región es la misma, independientemente del orden en que la recorras, así que una cola (búsqueda en anchura) y una pila (búsqueda en profundidad) pintan los mismos píxeles. Elige la opción que sea más breve de escribir en tu lenguaje y evita la recursión en imágenes grandes.

¿Por qué Flood Fill entra en un bucle infinito cuando el nuevo color es igual al anterior?

La solución habitual interpreta «sigue teniendo el color antiguo» como «todavía no se ha visitado». Cuando el nuevo color es igual al antiguo, pintar un píxel no lo cambia, así que sus píxeles vecinos lo vuelven a añadir a la pila y la búsqueda nunca termina. Comprobar primero este caso y devolver la imagen lo soluciona, y la imagen sin cambios es la respuesta correcta.

¿Se puede resolver Flood Fill de forma recursiva?

Sí, una función que pinta un píxel y se llama a sí misma para cada vecino del color antiguo es correcta. El riesgo está en la profundidad: la recursión alcanza una profundidad igual a la del camino más largo que sigue la búsqueda, que en una región sinuosa puede llegar a miles de llamadas. Una pila explícita realiza el mismo trabajo sin ese límite.

Python

def floodFill(image, sr, sc, color):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

Esperado

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]