Flood Fill

Q: Quelle est la complexité temporelle du remplissage par diffusion ?

O(m × n) pour une image de m lignes et n colonnes. Chaque pixel de la région est empilé une fois et examine quatre voisins, tandis que les pixels situés à l’extérieur de la région ne sont examinés qu’en tant que voisins. La pile peut contenir jusqu’à m × n pixels lorsque toute l’image forme une seule région.

Q: Faut-il utiliser BFS ou DFS pour le remplissage par diffusion ?

Les deux fonctionnent et prennent un temps O(m × n). La région est la même quel que soit l’ordre dans lequel vous la parcourez : une file (parcours en largeur) et une pile (parcours en profondeur) colorient les mêmes pixels. Choisissez la solution la plus courte à écrire dans votre langage et évitez la récursion sur les grandes images.

Q: Pourquoi Flood Fill boucle-t-il indéfiniment lorsque la nouvelle couleur est identique à l’ancienne ?

La solution habituelle considère que « a encore l’ancienne couleur » signifie « pas encore visité ». Lorsque la nouvelle couleur est identique à l’ancienne, peindre un pixel ne le modifie pas ; ses voisins le remettent donc sur la pile et la recherche ne se termine jamais. Vérifier d’abord ce cas et renvoyer l’image corrige le problème, et l’image inchangée est la bonne réponse.

Q: Peut-on résoudre le remplissage par propagation de manière récursive ?

Oui, une fonction qui peint un pixel et s’appelle elle-même pour chaque voisin de l’ancienne couleur est correcte. Le risque concerne la profondeur : la récursion atteint une profondeur égale à la longueur du plus long chemin suivi par la recherche, ce qui peut représenter des milliers d’appels dans une région sinueuse. Une pile explicite effectue le même travail sans cette limite.

FacileGraphes

+10

Une image est une grille de nombres entiers, où chaque nombre correspond à la couleur d’un pixel. L’image vous est fournie sous forme d’une liste de lignes, avec un pixel de départ à la ligne sr et à la colonne sc, ainsi qu’une nouvelle color. Recolorez la région qui contient le pixel de départ : chaque pixel de la même couleur que celui-ci que vous pouvez atteindre en vous déplaçant vers le haut, le bas, la gauche ou la droite à travers des pixels de cette même couleur. Renvoyez l’image après la recoloration.

Fonction

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

imageinteger-2d-array: l’image sous forme de liste de lignes, un nombre par pixel
srinteger: la ligne du pixel de départ, comptée à partir de 0
scinteger: la colonne du pixel de départ, comptée à partir de 0
colorinteger: la nouvelle couleur de la région
Renvoieinteger-2d-array: l’image après le repeint de la région

Contraintes

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Chaque ligne a la même longueur.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length et 0 ≤ sc < image[0].length

Exemples

Entrée: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Sortie: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Explication: Le point de départ contient la couleur 1. Le 1 à sa droite, les 1 de la colonne de gauche et de la rangée du bas, ainsi que le 1 au-dessus du coin inférieur droit, lui sont reliés : les sept deviennent donc des 5. Les deux 0 sont d’une couleur différente et la conservent.

+18 tests cachés à la soumission

Pour aller plus loin

Comment votre solution changerait-elle si les pixels qui se touchent uniquement par un coin étaient également considérés comme connectés ?

Solution

La région est une partie connexe d’un graphe : les pixels sont des nœuds, et deux pixels de la couleur de départ qui partagent un côté sont reliés. Toute recherche qui commence au pixel donné et ne parcourt que cette couleur trouve toute la région. Les deux pièges sont une image où la nouvelle couleur est identique à l’ancienne, et une longue région sinueuse qui fait échouer une recherche récursive.

Recherche en profondeur récursive

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Écrivez une fonction paint(r, c) qui fait une seule petite chose : si (r, c) se trouve dans l’image et a encore l’ancienne couleur, elle lui donne la nouvelle couleur et s’appelle sur les quatre voisins. Un seul appel sur le pixel de départ se propage à toute la région, car chaque pixel de la région est relié au point de départ par un chemin de pixels de l’ancienne couleur, et les appels suivent ce chemin.

Peindre le pixel avant les quatre appels empêche la propagation de tourner en rond : lorsqu’un voisin rappelle une fonction sur un pixel déjà peint, la couleur ne correspond plus et l’appel se termine aussitôt. Cela ne fonctionne que si la nouvelle couleur est différente de l’ancienne ; vérifiez donc cela d’abord et renvoyez l’image inchangée si elles sont identiques.

Le travail est en O(m × n), mais la pile d’appels est le point faible. La récursion va aussi loin que le chemin qu’elle suit. Un serpent d’un pixel de largeur dans une image de 80 × 80 fait environ 3 200 pixels de long, donc les appels s’imbriquent sur environ 3 200 niveaux. Python s’arrête à 1 000 par défaut et déclenche une erreur, ce qui explique pourquoi cette approche ne termine pas les tests les plus grands. D’autres langages autorisent des appels plus profonds, mais une image plus grande épuiserait aussi leur pile d’appels.

Algorithme

Lisez old = image[sr][sc]. Si old est égal à color, renvoyez l’image.
Définissez paint(r, c) : retournez si (r, c) est en dehors de l’image ou si sa couleur n’est pas old.
Sinon, définissez image[r][c] = color et appelez paint sur les pixels du dessus, du dessous, de gauche et de droite.
Appelez paint(sr, sc) et renvoyez l’image.

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

Recherche en profondeur avec une pile explicite

Intuition

Effectuez le même parcours, mais gardez les pixels restant à visiter dans une pile que vous gérez vous-même plutôt que dans la pile d’appels. Coloriez le pixel de départ et empilez-le. Dépilez un pixel, examinez ses quatre voisins et, pour chaque voisin situé dans l’image qui a encore l’ancienne couleur, coloriez-le et empilez-le. Lorsque la pile est vide, toute la région est coloriée.

Coloriez un pixel lorsque vous l’empilez, et non lorsque vous le dépilez. Un pixel colorié n’a plus l’ancienne couleur, donc la vérification de la couleur sert aussi à vérifier s’il a déjà été visité : aucun pixel n’entre deux fois dans la pile, et vous n’avez pas besoin d’une grille distincte de marqueurs. Comme dans la version récursive, la nouvelle couleur doit être différente de l’ancienne ; renvoyez donc l’image inchangée si elles sont identiques.

Chaque pixel de la région est empilé une fois et ses quatre voisins sont vérifiés, donc le temps d’exécution est O(m × n). La pile contient au maximum les pixels de la région. Elle se trouve dans la mémoire ordinaire ; une région sinueuse de 3,200 pixels ne pose donc aucun problème, contrairement à la version récursive qui a épuisé la pile d’appels.

Algorithme

Lisez old = image[sr][sc]. Si old est égal à color, retournez l’image.
Coloriez (sr, sc) et empilez-le.
Dépilez un pixel et examinez ses quatre voisins.
Pour chaque voisin situé dans l’image et dont la couleur est old, coloriez-le et empilez-le.
Lorsque la pile est vide, retournez l’image.

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

Pièges et cas limites

La plupart des mauvaises réponses sont dues au même cas de couleur, au fait de sortir de l’image ou à la récursion sur une grande région.

Oublier le cas où color est égal à la couleur de départ. La peinture ne change alors rien : une recherche qui utilise la couleur comme marqueur de pixels visités empile les mêmes pixels à l’infini.
Lire image[sr][sc] après l’avoir peint. Enregistre d’abord l’ancienne couleur, sinon tu compareras chaque voisin à la nouvelle couleur.
Compter les voisins en diagonale. Les pixels qui ne se touchent que par un coin ne sont pas connectés.
Vérifier la couleur d’un voisin avant de vérifier qu’il se trouve dans l’image. Vérifie d’abord 0 ≤ row < rows et 0 ≤ col < cols.
Utiliser la récursion sur une grande image. Un chemin d’un pixel de large dans une image de 80 × 80 mesure environ 3 200 pixels, une profondeur suffisante pour dépasser la limite de récursion de Python.
Peindre tous les pixels de l’ancienne couleur dans l’image entière. Les pixels de cette couleur qui sont isolés du point de départ doivent conserver leur couleur.

Questions fréquentes4

Quelle est la complexité temporelle du remplissage par diffusion ?

O(m × n) pour une image de m lignes et n colonnes. Chaque pixel de la région est empilé une fois et examine quatre voisins, tandis que les pixels situés à l’extérieur de la région ne sont examinés qu’en tant que voisins. La pile peut contenir jusqu’à m × n pixels lorsque toute l’image forme une seule région.

Faut-il utiliser BFS ou DFS pour le remplissage par diffusion ?

Les deux fonctionnent et prennent un temps O(m × n). La région est la même quel que soit l’ordre dans lequel vous la parcourez : une file (parcours en largeur) et une pile (parcours en profondeur) colorient les mêmes pixels. Choisissez la solution la plus courte à écrire dans votre langage et évitez la récursion sur les grandes images.

Pourquoi Flood Fill boucle-t-il indéfiniment lorsque la nouvelle couleur est identique à l’ancienne ?

La solution habituelle considère que « a encore l’ancienne couleur » signifie « pas encore visité ». Lorsque la nouvelle couleur est identique à l’ancienne, peindre un pixel ne le modifie pas ; ses voisins le remettent donc sur la pile et la recherche ne se termine jamais. Vérifier d’abord ce cas et renvoyer l’image corrige le problème, et l’image inchangée est la bonne réponse.

Peut-on résoudre le remplissage par propagation de manière récursive ?

Oui, une fonction qui peint un pixel et s’appelle elle-même pour chaque voisin de l’ancienne couleur est correcte. Le risque concerne la profondeur : la récursion atteint une profondeur égale à la longueur du plus long chemin suivi par la recherche, ce qui peut représenter des milliers d’appels dans une région sinueuse. Une pile explicite effectue le même travail sans cette limite.

Python

def floodFill(image, sr, sc, color):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

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