Codice vernice MS chiesto in un'intervista

Question

Oggi ho avuto un'intervista e mi è stata fatta questa domanda!

codice del programma MS Paint. Area N * N pixel. dati pixel e colori, cambia colore in pixel al colore desiderato e se i pixel adiacenti sono dello stesso colore, cambialo anche loro.

mi sono avvicinato dicendo che prendo un array n * n e controllerei il pixel dato e passerò al adiacente. per esempio il pixel dato è x, yi dovrebbe prima verificare il colore in x, y nella matrice e successivamente cercare (x + 1, y + 1), (x + 1, y), (x, y + 1), (x-1, y), (x-1, y-1) ....

ma l'intervistatore non era felice qualcuno può suggerirmi un altro modo con un algoritmo migliore .. che ha spazio e complessità temporale!

Answer 1

L'intervistatore stava probabilmente chiedendo il riempimento, che non può essere fatto con un approccio così semplice.

Se si tratta di riempimento, la diagonale non conta come adiacente.

Il riempimento di riempimento più semplice è una chiamata ricorsiva su ciascun pixel adiacente nell'array. È molto probabile che l'utilizzo semplice di una grande griglia finisca in una pila.

Il modo giusto è quello di accodare la posizione di partenza, quindi dequeue, controllare se il colore dei pixel è ancora colore di origine, e la scansione di riempimento a destra ea sinistra, come si va, e accodare tutti i pixel sopra e sotto. Continua fino alla fine della coda.

Answer 2

L'algoritmo di cui parli si chiama riempimento. approcci Ben noti sono discussi in Wikipedia.

Answer 3

È possibile utilizzare DFS algoritmo per risolvere questo problema. Dato un pixel (xi, yi), puoi sempre costruire il grafico in modo tale che il nodo di pixel (xi-1, yi-1), (xi-1, yi), (xi, yi + 1), (xi + 1, yi), (xi + 1, yi-1), (xi + 1, yi + 1), (xi-1, yi + 1) e (xi, yi-1) come nodi di pixel adiacenti a (xi, yi) . Esegui il DFS partendo dal nodo (xi, yi) colorando ciascun nodo nel percorso e tornando indietro una volta raggiunto un diverso nodo di colore. DFS ha una buona complessità temporale di O (V + E).