Flood Fill

Q: Qual è la complessità temporale del riempimento Flood Fill?

O(m × n) per un'immagine con m righe e n colonne. Ogni pixel della regione viene inserito una volta nello stack e controlla quattro pixel adiacenti, mentre i pixel esterni alla regione vengono controllati solo come pixel adiacenti. Lo stack può contenere fino a m × n pixel quando l'intera immagine costituisce un'unica regione.

Q: È meglio usare BFS o DFS per il riempimento delle aree?

Entrambi vanno bene e richiedono un tempo O(m × n). La regione è la stessa indipendentemente dall’ordine in cui la visiti, quindi una coda (in ampiezza) e una pila (in profondità) colorano gli stessi pixel. Scegli quello che è più breve da scrivere nel tuo linguaggio ed evita la ricorsione sulle immagini grandi.

Q: Perché Flood Fill continua a ripetersi all'infinito quando il nuovo colore è uguale a quello vecchio?

La soluzione usuale interpreta «ha ancora il vecchio colore» come «non ancora visitato». Quando il nuovo colore è uguale al vecchio, colorare un pixel non lo modifica, quindi i pixel vicini lo reinseriscono nello stack e la ricerca non termina mai. Controllare prima questo caso e restituire l’immagine risolve il problema, e l’immagine invariata è la risposta corretta.

Q: Flood Fill può essere risolto in modo ricorsivo?

Sì, una funzione che colora un pixel e richiama sé stessa su ogni vicino del vecchio colore è corretta. Il rischio è la profondità: la ricorsione arriva fino alla lunghezza del percorso più lungo seguito dalla ricerca, che in una regione tortuosa può raggiungere migliaia di chiamate. Uno stack esplicito svolge lo stesso lavoro senza questo limite.

FacileGrafi

+10

Un'immagine è una griglia di numeri interi, in cui ogni numero rappresenta il colore di un pixel. Ricevi l'immagine come un elenco di righe, un pixel iniziale alla riga sr e alla colonna sc, e un nuovo color. Ridipingi la regione che contiene il pixel iniziale: tutti i pixel dello stesso colore del pixel iniziale che puoi raggiungere da esso spostandoti in alto, in basso, a sinistra o a destra attraverso pixel dello stesso colore. Restituisci l'immagine dopo averla ridipinta.

Funzione

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

imageinteger-2d-array: l'immagine come un elenco di righe, un numero per pixel
srinteger: la riga del pixel iniziale, contando da 0
scinteger: la colonna del pixel iniziale, contando da 0
colorinteger: il nuovo colore per la regione
Restituisceinteger-2d-array: l'immagine dopo che la regione viene ridisegnata

Vincoli

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Ogni riga ha la stessa lunghezza.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length and 0 ≤ sc < image[0].length

Esempi

Input: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Output: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Spiegazione: Il punto di partenza contiene il colore 1. L'1 alla sua destra, gli 1 lungo la colonna di sinistra e la riga in basso, e l'1 sopra l'angolo in basso a destra sono tutti collegati a esso, quindi tutti e sette diventano 5. I due 0 sono di un colore diverso e rimangono tali.

+18 test nascosti all’invio

Per approfondire

Come cambierebbe la tua soluzione se anche i pixel che si toccano solo in un angolo fossero considerati connessi?

Soluzione

La regione è una parte connessa di un grafo: i pixel sono nodi e due pixel del colore iniziale che condividono un lato sono collegati. Qualsiasi ricerca che inizi dal pixel indicato e proceda solo attraverso quel colore trova l'intera regione. Le due insidie sono un'immagine in cui il nuovo colore è uguale a quello vecchio e una regione lunga e tortuosa che interrompe una ricerca ricorsiva.

Ricerca in profondità ricorsiva

Corretto, ma non termina sui test più grandi

Intuizione

Scrivi una funzione paint(r, c) che fa una piccola cosa: se (r, c) si trova all'interno dell'immagine e ha ancora il vecchio colore, assegnale il nuovo colore e chiamala sui quattro vicini. Una chiamata sul pixel iniziale si propaga in tutta la regione, perché ogni pixel della regione è collegato all'inizio da un percorso di pixel del vecchio colore e le chiamate seguono quel percorso.

Dipingere il pixel prima delle quattro chiamate è ciò che impedisce alla propagazione di girare in tondo: quando un vicino richiama un pixel già dipinto, il colore non corrisponde più e la chiamata termina subito. Funziona solo quando il nuovo colore è diverso da quello vecchio, quindi controlla prima e restituisci l'immagine invariata quando sono uguali.

Il lavoro è O(m × n), ma lo stack delle chiamate è il punto debole. La ricorsione arriva a una profondità pari alla lunghezza del percorso che sta seguendo. Un serpente largo un pixel che attraversa un'immagine di 80 × 80 è lungo circa 3,200 pixel, quindi le chiamate si annidano per circa 3,200 livelli. Python si ferma per impostazione predefinita a 1,000 e genera un errore, ed è per questo che questo approccio non termina sui test più grandi. Altri linguaggi consentono chiamate più profonde, ma un'immagine più grande esaurirebbe comunque anche il loro stack delle chiamate.

Algoritmo

Leggi old = image[sr][sc]. Se old è uguale a color, restituisci l'immagine.
Definisci paint(r, c): termina se (r, c) è fuori dall'immagine o il suo colore non è old.
Altrimenti imposta image[r][c] = color e chiama paint sui pixel sopra, sotto, a sinistra e a destra.
Chiama paint(sr, sc) e restituisci l'immagine.

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

Ricerca in profondità con uno stack esplicito

Intuizione

Esegui la stessa visita, ma tieni i pixel ancora da visitare in una pila di tua proprietà invece che nello stack delle chiamate. Colora il pixel iniziale e inseriscilo nella pila. Estrai un pixel, osserva i suoi quattro vicini e, per ciascun vicino all'interno dell'immagine che ha ancora il vecchio colore, coloralo e inseriscilo nella pila. Quando la pila è vuota, hai colorato tutta la regione.

Colora un pixel quando lo inserisci nella pila, non quando lo estrai. Un pixel colorato non ha più il vecchio colore, quindi il controllo del colore funge anche da controllo dei pixel visitati: nessun pixel entra due volte nella pila e non ti serve una griglia separata di contrassegni. Come nella versione ricorsiva, il nuovo colore deve essere diverso da quello vecchio, quindi restituisci l'immagine invariata quando sono uguali.

Ogni pixel della regione viene inserito una volta nella pila e vengono controllati i suoi quattro vicini, quindi il tempo è O(m × n). La pila contiene al massimo i pixel della regione. Si trova nella memoria ordinaria, quindi una regione tortuosa di 3,200 pixel non è un problema, mentre la versione ricorsiva esauriva lo stack delle chiamate.

Algoritmo

Leggi old = image[sr][sc]. Se old è uguale a color, restituisci l’immagine.
Colora (sr, sc) e inseriscilo in uno stack.
Estrai un pixel dallo stack e guarda i suoi quattro vicini.
Per ogni vicino all’interno dell’immagine il cui colore è old, coloralo e inseriscilo nello stack.
Quando lo stack è vuoto, restituisci l’immagine.

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

Trappole e casi limite

La maggior parte delle risposte sbagliate deriva dallo stesso caso di colore, dall’uscire dai limiti dell’immagine o dalla ricorsione su una regione estesa.

Dimenticare il caso in cui color è uguale al colore iniziale. In tal caso, la colorazione non cambia nulla, quindi una ricerca che usa il colore come marcatore di pixel visitati inserisce gli stessi pixel all’infinito.
Leggere image[sr][sc] dopo averlo colorato. Salva prima il colore originale, altrimenti confronterai ogni vicino con il nuovo colore.
Contare i vicini diagonali. I pixel che si toccano solo in un angolo non sono connessi.
Controllare il colore di un vicino prima di verificare che si trovi all’interno dell’immagine. Verifica prima 0 ≤ row < rows e 0 ≤ col < cols.
Usare la ricorsione su un’immagine grande. Un percorso largo un pixel in un’immagine di 80 × 80 è lungo circa 3,200 pixel, abbastanza da superare il limite di ricorsione di Python.
Colorare tutti i pixel del colore originale nell’intera immagine. I pixel di quel colore che sono isolati dal punto iniziale devono conservare il loro colore.

Domande frequenti4

Qual è la complessità temporale del riempimento Flood Fill?

O(m × n) per un'immagine con m righe e n colonne. Ogni pixel della regione viene inserito una volta nello stack e controlla quattro pixel adiacenti, mentre i pixel esterni alla regione vengono controllati solo come pixel adiacenti. Lo stack può contenere fino a m × n pixel quando l'intera immagine costituisce un'unica regione.

È meglio usare BFS o DFS per il riempimento delle aree?

Entrambi vanno bene e richiedono un tempo O(m × n). La regione è la stessa indipendentemente dall’ordine in cui la visiti, quindi una coda (in ampiezza) e una pila (in profondità) colorano gli stessi pixel. Scegli quello che è più breve da scrivere nel tuo linguaggio ed evita la ricorsione sulle immagini grandi.

Perché Flood Fill continua a ripetersi all'infinito quando il nuovo colore è uguale a quello vecchio?

La soluzione usuale interpreta «ha ancora il vecchio colore» come «non ancora visitato». Quando il nuovo colore è uguale al vecchio, colorare un pixel non lo modifica, quindi i pixel vicini lo reinseriscono nello stack e la ricerca non termina mai. Controllare prima questo caso e restituire l’immagine risolve il problema, e l’immagine invariata è la risposta corretta.

Flood Fill può essere risolto in modo ricorsivo?

Sì, una funzione che colora un pixel e richiama sé stessa su ogni vicino del vecchio colore è corretta. Il rischio è la profondità: la ricorsione arriva fino alla lunghezza del percorso più lungo seguito dalla ricerca, che in una regione tortuosa può raggiungere migliaia di chiamate. Uno stack esplicito svolge lo stesso lavoro senza questo limite.

Python

def floodFill(image, sr, sc, color):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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