Ich hatte heute ein Interview und wurde diese Frage gestellt!
kodieren Sie das MS Paint Programm. N * N Pixelbereich. gegebenes Pixel und Farbe, ändern Sie Farbe in Pixel zur gewünschten Farbe und wenn benachbarte Pixel von der gleichen Farbe sind, ändern Sie sie auch.
Ich habe mich ihm genähert, indem ich gesagt habe, dass ich ein n * n-Array nehmen werde und nach dem gegebenen Pixel suchen werde und in das benachbarte verschieben werde. Wenn zum Beispiel das gegebene Pixel x ist, würde yi zuerst nach der Farbe in x, y im Array suchen und dann nach (x + 1, y + 1), (x + 1, y), (x, y + 1) suchen ), (x-1, y), (x-1, y-1) ....
aber der Interviewer war nicht glücklich, kann mir jemand einen anderen Weg vorschlagen mit einem besseren Algorithmus .. der eine bessere räumliche und zeitliche Komplexität hat!
Der Interviewer hat wahrscheinlich nach einer Flutfüllung gefragt, was mit einem so einfachen Ansatz nicht möglich ist.
Wenn dies eine Flutfüllung ist, zählt die Diagonale nicht als benachbart.
Die einfachste Flutfüllung ist ein rekursiver Aufruf an jedem benachbarten Pixel im Array. Die Verwendung des einfachen Wegs auf einem großen Gitter ist sehr wahrscheinlich ohne Stapel.
Der richtige Weg besteht darin, die Startposition in die Warteschlange einzureihen, dann die Warteschlange zu entfernen, zu überprüfen, ob die Pixelfarbe noch Quellfarbe ist, und während des Kopiervorgangs nach links und rechts zu scannen und alle Pixel oben und unten in die Warteschlange einzureihen. Fahren Sie fort, bis die Warteschlange leer ist.
Der Algorithmus, von dem Sie sprechen, heißt flood fill. Bekannte Ansätze werden auf Wikipedia diskutiert .
Sie können das DFS -Algorithmus verwenden, um dieses Problem zu lösen. Gegeben ein Pixel (xi, yi), Sie können den Graphen immer so konstruieren, dass der Pixelknoten (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) und (xi, yi-1) als benachbarte Pixelknoten zu (xi, yi) . Führen Sie das DFS beginnend mit dem Knoten (xi, yi) aus, indem Sie jeden Knoten im Pfad farbig markieren und zurückverfolgen, sobald Sie auf einen anderen Farbknoten treffen. DFS hat eine gute Zeit Komplexität von O (V + E).
Tags und Links algorithm