Kod farby MS zadany w wywiadzie

Question

Miałem dzisiaj wywiad i zadano mu to pytanie!

zakodować program MS Paint. Obszar N * N pikseli. dany piksel i kolor, zmień kolor w pikselach na pożądany kolor i jeśli sąsiednie piksele mają ten sam kolor, zmień je również.

Podszedłem do tego, mówiąc, że wezmę tablicę n * n i sprawdzę podany piksel i przejdę do sąsiedniego. na przykład podany piksel to x, yi najpierw sprawdziłby kolor wx, y w tablicy i następnym wyszukiwaniu (x + 1, y + 1), (x + 1, y), (x, y + 1), (x-1, y), (x-1, y-1) ....

ale ankieter nie był zadowolony, czy ktoś może zaproponować mi inny sposób z lepszym algorytmem .. który ma lepszą przestrzeń i złożoność czasu!

Answer 1

Osoba przeprowadzająca wywiad prawdopodobnie prosiła o wypełnienie powodzi, czego nie można zrobić przy tak prostym podejściu.

Jeśli jest to wypełnienie zalewowe, przekątna nie jest traktowana jako sąsiednia.

Najprostszym wypełnieniem powodziowym jest wywołanie rekurencyjne na każdym sąsiadującym pikselu w tablicy. Korzystanie z prostego sposobu na dużej siatce bardzo prawdopodobnie zabraknie sterty.

Właściwy sposób polega na wpisaniu początkowej lokalizacji, a następnie usunięciu z kolejki, sprawdzeniu, czy kolor piksela jest nadal kolorem źródłowym, a następnie skanowaniu lewego i prawego wypełnienia podczas przechodzenia, a następnie wstawiania wszystkich pikseli powyżej i poniżej. Kontynuuj, dopóki kolejka nie zostanie opróżniona.

Answer 2

Algorytm, o którym mówisz, nazywa się wypełnieniem powodziowym . Znane podejścia są omówione w Wikipedia.

Answer 3

Można użyć DFS algorytmu do rozwiązania tego problemu. Biorąc pod uwagę piksel (xi, yi), zawsze możesz zbudować wykres taki, że węzeł pikseli (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) i (xi, yi-1) jako sąsiednie węzły pikseli do (xi, yi) . Wykonywanie operacji zaczynając od węzła (xi, yi), kolorując każdy węzeł na ścieżce i przechodząc wstecz po trafieniu w inny węzeł koloru. DFS ma dobrą złożoność czasu O (V + E).