Flood Fill

Q: Jaka jest złożoność czasowa algorytmu Flood Fill?

O(m × n) dla obrazu o m wierszach i n kolumnach. Każdy piksel regionu jest raz umieszczany na stosie i sprawdzane są jego cztery sąsiednie piksele, a piksele spoza regionu są sprawdzane tylko jako sąsiedzi. Stos może pomieścić do m × n pikseli, gdy cały obraz stanowi jeden region.

Q: Czy do wypełniania obszaru należy użyć BFS czy DFS?

Oba rozwiązania działają i mają złożoność czasową O(m × n). Obszar jest taki sam niezależnie od kolejności jego odwiedzania, więc kolejka (wszerz) i stos (w głąb) zamalują te same piksele. Wybierz rozwiązanie, które łatwiej zapisać w Twoim języku, i unikaj rekurencji w przypadku dużych obrazów.

Q: Dlaczego Flood Fill zapętla się w nieskończoność, gdy nowy kolor jest taki sam jak stary?

Typowe rozwiązanie traktuje „nadal ma stary kolor” jako „jeszcze nieodwiedzony”. Gdy nowy kolor jest taki sam jak stary, pomalowanie piksela nie zmienia go, więc jego sąsiedzi ponownie dodają go na stos, a wyszukiwanie nigdy się nie kończy. Najpierw sprawdzenie tego przypadku i zwrócenie obrazu rozwiązuje problem, a niezmieniony obraz jest poprawną odpowiedzią.

Q: Czy Flood Fill można rozwiązać rekurencyjnie?

Tak, funkcja, która zamalowuje piksel i wywołuje samą siebie dla każdego sąsiada w starym kolorze, jest poprawna. Ryzykiem jest głębokość: rekurencja sięga tak głęboko, jak najdłuższa ścieżka przebyta podczas wyszukiwania, co w krętym obszarze może oznaczać tysiące wywołań. Jawny stos wykonuje tę samą pracę bez tego ograniczenia.

ŁatweGrafy

+10

Obraz to siatka liczb całkowitych, w której każda liczba oznacza kolor jednego piksela. Otrzymujesz obraz jako listę wierszy, piksel początkowy w wierszu sr i kolumnie sc oraz nowy color. Przemaluj region zawierający piksel początkowy: każdy piksel w kolorze piksela początkowego, do którego można dotrzeć z niego, przechodząc w górę, w dół, w lewo lub w prawo przez piksele tego samego koloru. Zwróć obraz po przemalowaniu.

Funkcja

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

imageinteger-2d-array: obraz jako lista wierszy, po jednej liczbie na piksel
srinteger: wiersz początkowego piksela, liczony od 0
scinteger: kolumna pikselu początkowego, liczona od 0
colorinteger: nowy kolor regionu
Zwracainteger-2d-array: obraz po ponownym narysowaniu regionu

Ograniczenia

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Każdy wiersz ma tę samą długość.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length oraz 0 ≤ sc < image[0].length

Przykłady

Wejście: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Wyjście: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Wyjaśnienie: Początkowe pole ma kolor 1. Pole 1 po jego prawej stronie, pola 1 wzdłuż lewej kolumny i dolnego wiersza oraz pole 1 nad prawym dolnym rogiem są z nim połączone, więc wszystkie siedem pól zmienia kolor na 5. Dwa pola 0 mają inny kolor, więc pozostają bez zmian.

+18 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak zmieniłoby się Twoje rozwiązanie, gdyby piksele stykające się tylko narożnikiem również były uznawane za połączone?

Rozwiązanie

Obszar to spójna część grafu: piksele są węzłami, a dwa piksele w kolorze początkowym, które mają wspólny bok, są połączone. Każde wyszukiwanie rozpoczynające się w podanym pikselu i przechodzące tylko przez piksele tego koloru znajduje cały obszar. Dwie pułapki to obraz, na którym nowy kolor jest taki sam jak stary, oraz długi, kręty obszar, który powoduje przerwanie rekurencyjnego wyszukiwania.

Rekurencyjne przeszukiwanie w głąb

Poprawne, ale nie kończy się na największych testach

Intuicja

Napisz funkcję paint(r, c), która robi jedną małą rzecz: jeśli (r, c) znajduje się wewnątrz obrazu i nadal ma stary kolor, nadaj mu nowy kolor i wywołaj ją dla czterech sąsiadów. Jedno wywołanie dla początkowego piksela rozprzestrzenia się na cały region, ponieważ każdy piksel regionu jest połączony ze стартowym ścieżką z pikseli o starym kolorze, a wywołania podążają tą ścieżką.

Pomalowanie piksela przed czterema wywołaniami zapobiega rozprzestrzenianiu się w kółko: gdy sąsiad wywoła ponownie funkcję dla pomalowanego piksela, kolor już się nie zgadza, więc wywołanie natychmiast się kończy. Działa to tylko wtedy, gdy nowy kolor różni się od starego, więc najpierw to sprawdź i zwróć obraz bez zmian, jeśli kolory są takie same.

Złożoność wynosi O(m × n), ale słabym punktem jest stos wywołań. Rekurencja osiąga głębokość równą długości ścieżki, którą podąża. Wąż o szerokości jednego piksela wijący się przez obraz 80 × 80 ma długość około 3,200 pikseli, więc wywołania zagnieżdżają się na głębokość około 3,200. Python domyślnie zatrzymuje się na 1,000 i zgłasza błąd, dlatego to podejście nie kończy się poprawnie dla największych testów. Inne języki pozwalają na głębsze wywołania, ale większy obraz również wyczerpałby ich stos wywołań.

Algorytm

Odczytaj old = image[sr][sc]. Jeśli old jest równe color, zwróć obraz.
Zdefiniuj paint(r, c): zakończ, jeśli (r, c) znajduje się poza obrazem lub jego kolor nie jest równy old.
W przeciwnym razie ustaw image[r][c] = color i wywołaj paint dla pikseli powyżej, poniżej, po lewej i po prawej stronie.
Wywołaj paint(sr, sc) i zwróć obraz.

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

Przeszukiwanie w głąb z jawnym stosem

Intuicja

Wykonaj ten sam obchód, ale przechowuj piksele, które pozostały do odwiedzenia, na własnym stosie zamiast na stosie wywołań. Pokoloruj piksel początkowy i umieść go na stosie. Zdejmij piksel ze stosu, sprawdź jego czterech sąsiadów, a każdego sąsiada znajdującego się w obrazie i mającego jeszcze stary kolor pokoloruj i umieść na stosie. Gdy stos będzie pusty, cały region będzie pokolorowany.

Pokoloruj piksel w chwili umieszczania go na stosie, a nie zdejmowania ze stosu. Pokolorowany piksel nie ma już starego koloru, więc sprawdzenie koloru służy jednocześnie do sprawdzenia, czy piksel został odwiedzony: żaden piksel nie trafi na stos dwa razy i nie potrzebujesz osobnej siatki oznaczeń. Podobnie jak w wersji rekurencyjnej, nowy kolor musi różnić się od starego, więc jeśli są takie same, zwróć obraz bez zmian.

Każdy piksel regionu jest umieszczany na stosie raz i sprawdzani są jego czterej sąsiedzi, więc czas działania wynosi O(m × n). Stos przechowuje najwyżej tyle pikseli, ile jest w regionie. Zajmuje zwykłą pamięć, więc kręty region o wielkości 3,200 pikseli nie stanowi problemu, podczas gdy wersji rekurencyjnej zabrakło miejsca na stosie wywołań.

Algorytm

Odczytaj old = image[sr][sc]. Jeśli old jest równe color, zwróć obraz.
Pokoloruj (sr, sc) i umieść go na stosie.
Zdejmij piksel ze stosu i sprawdź jego czterech sąsiadów.
Dla każdego sąsiada znajdującego się w obrazie, którego kolor to old, pokoloruj go i umieść na stosie.
Gdy stos będzie pusty, zwróć obraz.

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

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z tego samego przypadku koloru, opuszczenia obrazu albo rekurencji w dużym regionie.

Pomijanie przypadku, w którym color jest równy kolorowi początkowemu. Malowanie nic wtedy nie zmienia, więc wyszukiwanie, które używa koloru jako oznaczenia odwiedzonych pikseli, dodaje w kółko te same piksele.
Odczytywanie image[sr][sc] po jego przemalowaniu. Najpierw zapisz stary kolor, bo w przeciwnym razie każdy sąsiedni piksel będzie porównywany z nowym kolorem.
Liczenie sąsiadów po przekątnej. Piksele stykające się tylko narożnikami nie są połączone.
Sprawdzanie koloru sąsiedniego piksela przed sprawdzeniem, czy znajduje się on wewnątrz obrazu. Najpierw sprawdź 0 ≤ row < rows i 0 ≤ col < cols.
Rekurencja w dużym obrazie. Ścieżka o szerokości jednego piksela przez obraz o wymiarach 80 × 80 ma około 3,200 pikseli długości, co wystarcza, by przekroczyć limit rekurencji Pythona.
Przemalowywanie wszystkich pikseli starego koloru w całym obrazie. Piksele tego koloru odcięte od punktu początkowego muszą zachować swój kolor.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu Flood Fill?

O(m × n) dla obrazu o m wierszach i n kolumnach. Każdy piksel regionu jest raz umieszczany na stosie i sprawdzane są jego cztery sąsiednie piksele, a piksele spoza regionu są sprawdzane tylko jako sąsiedzi. Stos może pomieścić do m × n pikseli, gdy cały obraz stanowi jeden region.

Czy do wypełniania obszaru należy użyć BFS czy DFS?

Oba rozwiązania działają i mają złożoność czasową O(m × n). Obszar jest taki sam niezależnie od kolejności jego odwiedzania, więc kolejka (wszerz) i stos (w głąb) zamalują te same piksele. Wybierz rozwiązanie, które łatwiej zapisać w Twoim języku, i unikaj rekurencji w przypadku dużych obrazów.

Dlaczego Flood Fill zapętla się w nieskończoność, gdy nowy kolor jest taki sam jak stary?

Typowe rozwiązanie traktuje „nadal ma stary kolor” jako „jeszcze nieodwiedzony”. Gdy nowy kolor jest taki sam jak stary, pomalowanie piksela nie zmienia go, więc jego sąsiedzi ponownie dodają go na stos, a wyszukiwanie nigdy się nie kończy. Najpierw sprawdzenie tego przypadku i zwrócenie obrazu rozwiązuje problem, a niezmieniony obraz jest poprawną odpowiedzią.

Czy Flood Fill można rozwiązać rekurencyjnie?

Tak, funkcja, która zamalowuje piksel i wywołuje samą siebie dla każdego sąsiada w starym kolorze, jest poprawna. Ryzykiem jest głębokość: rekurencja sięga tak głęboko, jak najdłuższa ścieżka przebyta podczas wyszukiwania, co w krętym obszarze może oznaczać tysiące wywołań. Jawny stos wykonuje tę samą pracę bez tego ograniczenia.

Python

def floodFill(image, sr, sc, color):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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