MS código de pintura en una entrevista

Question

¡Hoy tuve una entrevista y me hicieron esta pregunta!

codifique el programa MS Paint. N * N área de píxeles. dado el píxel y el color, cambie el color en píxel al color deseado y si los píxeles adyacentes son del mismo color también cambien.

lo abordé diciendo que tomaré una matriz n * n y comprobaría el píxel dado y me movería al adyacente. por ejemplo, el píxel dado es x, yi verificaría primero el color en x, y en la matriz y luego buscaría (x + 1, y + 1), (x + 1, y), (x, y + 1), (x-1, y), (x-1, y-1) ....

pero el entrevistador no estaba contento ¿alguien me puede sugerir de otra manera con un mejor algoritmo ... que tiene mejor espacio y ¡complejidad de tiempo!

Answer 1

El entrevistador probablemente estaba pidiendo inundación, lo que no se puede hacer con un enfoque tan simple.

Si esto es inundación, la diagonal no cuenta como adyacente.

El relleno de inundación más simple es una llamada recursiva en cada píxel adyacente de la matriz. Usar la forma simple en una grilla grande es muy probable que se quede sin pila.

La forma correcta es poner en cola la ubicación de inicio, luego quitar la cola, verificar si el color del píxel sigue siendo el color de la fuente y escanear el relleno a izquierda y derecha sobre la marcha, y poner en cola todos los píxeles arriba y abajo. Continúe hasta que la cola se agote.

Answer 2

El algoritmo del que está hablando se llama flood fill. enfoques conocidos se discuten en Wikipedia.

Answer 3

Puede utilizar DFS algoritmo para resolver este problema. Dado un píxel (xi, yi), siempre puede construir el gráfico de modo que el nodo de píxel (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) y (xi, yi-1) como nodos de píxeles adyacentes a (xi, yi) . Ejecute DFS comenzando desde el nodo (xi, yi) para colorear cada nodo en la ruta y retroceder una vez que golpea un nodo de color diferente. DFS tiene una buena complejidad temporal de O (V + E).