Number of Islands

Q: Jaka jest złożoność czasowa problemu „Number of Islands”?

O(rows × cols). Skanowanie sprawdza każde pole raz, a każde pole lądu trafia na stos lub do kolejki raz i sprawdza czterech sąsiadów. Oznaczenia odwiedzonych pól oraz stos lub kolejka zajmują O(rows × cols) miejsca na mapie, która w całości składa się z lądu.

Q: Czy w przypadku problemu liczby wysp użyć BFS czy DFS?

Oba rozwiązania są poprawne pod względem czasu i pamięci, ponieważ wystarczy oznaczyć każde pole wyspy. BFS z kolejką nigdy nie używa rekurencji; DFS jest równie bezpieczny, gdy używa jawnego stosu.

Q: Czy potrafisz rozwiązać problem liczby wysp za pomocą struktury union-find?

Tak. Umieść każde pole lądu w osobnym zbiorze i rozpocznij liczenie od liczby pól lądu. Połącz każdą parę sąsiadujących pól lądu i zmniejsz licznik o jeden za każdym razem, gdy połączenie scala dwa różne zbiory. Dzięki kompresji ścieżek czas działania jest zbliżony do O(rows × cols).

Q: Czy potrafisz policzyć wyspy bez osobnej tablicy odwiedzonych pól?

Tak, jeśli możesz zmieniać mapę: zamieniaj każde pole lądu na wodę, gdy tylko do niego dotrzesz. W wielu językach nie można zmieniać ciągów znaków w miejscu, więc najpierw kopiujesz wiersze do siatki znaków, co zajmuje tyle samo miejsca co znaczniki odwiedzonych pól.

ŚrednieGrafy

+10

Otrzymujesz mapę w postaci listy ciągów znaków o jednakowej długości, gdzie '1' oznacza kwadrat lądu, a '0' — kwadrat wody. Dwa kwadraty lądu należą do tej samej wyspy, jeśli stykają się bokiem: od góry, dołu, lewej lub prawej strony. Kwadraty stykające się tylko narożnikiem nie są połączone. Zwróć liczbę wysp.

Funkcja

numIslands(grid: string-array) → integer

gridstring-array: mapa, jeden ciąg znaków w każdym wierszu
Zwracainteger: liczba wysp

Ograniczenia

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Każdy wiersz ma tę samą długość.
Każdy znak to '0' lub '1'.

Przykłady

Wejście: grid = ["11000", "11000", "00100", "00011"]
Wyjście: 3
Wyjaśnienie: Cztery kwadraty w lewym górnym rogu tworzą jedną wyspę. Środkowy kwadrat w trzecim rzędzie styka się z nimi tylko rogiem, więc jest drugą wyspą. Para w prawym dolnym rogu to trzecia wyspa.

Pytanie dodatkowe

Ląd pojawia się teraz po jednym kwadracie na mapie wody. Czy potrafisz podać liczbę wysp po dodaniu każdego nowego kwadratu, nie przeszukując ponownie całej mapy?

Rozwiązanie

Traktuj każde pole lądu jako węzeł połączony z sąsiednimi polami lądu: wyspa to jeden spójny obszar. Przeskanuj mapę i za każdym razem, gdy trafisz na ląd, którego jeszcze nie widziałeś, policz nową wyspę i wypełnij ją algorytmem zalewania, oznaczając każde jej pole, aby skanowanie nie policzyło go ponownie.

Wypełnianie obszaru z jawnym stosem (DFS)

Intuicja

Niezaznaczone pole lądu nie może należeć do wyspy, którą już policzono, ponieważ podczas liczenia wyspy zaznacza się ją w całości. Zatem rozpoczyna nową wyspę. Własny stos pozwala oznaczyć resztę: każde zdjęte ze stosu pole dodaje na stos swoich niezaznaczonych sąsiadów będących lądem, a gdy stos jest pusty, cała wyspa jest oznaczona.

Własny stos ma znaczenie, ponieważ rekurencyjne wypełnianie może osiągnąć głębokość 22 500 wywołań na mapie 150 × 150 pokrytej lądem. Każde pole trafia na stos najwyżej raz i sprawdza czterech sąsiadów, więc czas działania wynosi O(rows × cols). Oznaczenia i stos zajmują O(rows × cols) pamięci, gdy cała mapa pokryta jest lądem.

Algorytm

Utwórz znacznik odwiedzenia dla każdego pola i ustaw licznik na 0.
Przeskanuj każde pole, pomijając wodę i pola, które zostały już odwiedzone.
Gdy trafisz na nieodwiedzony ląd, dodaj 1 do licznika, oznacz pole i umieść je na stosie.
Dopóki stos nie jest pusty, zdejmij z niego pole i umieść na stosie każdego sąsiada znajdującego się na mapie, który jest nieodwiedzonym lądem, oznaczając go przed umieszczeniem na stosie.
Zwróć licznik po zakończeniu skanowania.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Wypełnianie obszaru za pomocą kolejki (BFS)

Intuicja

Zliczanie działa tak samo; zmienia się tylko kolejność odwiedzania. Kolejka pobiera pola z początku i dodaje nieoznaczonych sąsiadów lądu na końcu, więc odwiedza wyspę pierścieniami: najpierw pierwsze pole, potem każde pole oddalone o jeden krok, a następnie o dwa kroki. Każde pole nadal jest odwiedzane raz, w czasie i przestrzeni O(rows × cols).

Kolejność pierścieniowa określa odległość każdego pola od punktu początkowego, więc ta sama pętla odpowiada na pytania o najkrótszą ścieżkę na siatce, przechowując jedną dodatkową liczbę dla każdego pola.

Algorytm

Utwórz znacznik odwiedzenia dla każdego pola i ustaw licznik na 0.
Przejdź przez każde pole, pomijając wodę i pola, które zostały już odwiedzone.
Na nieodwiedzonym lądzie zwiększ licznik o 1, oznacz pole i umieść je w pustej kolejce.
Gdy w kolejce są pola, weź jedno z początku i dodaj na końcu każdego sąsiada znajdującego się na mapie, który jest nieodwiedzonym lądem, oznaczając go przy dodawaniu.
Zwróć licznik po zakończeniu przeglądania.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Pułapki i przypadki brzegowe

Oznaczanie pola podczas zdejmowania go ze stosu lub kolejki zamiast podczas dodawania go do niej. Wtedy to samo pole trafia do niej kilka razy.
Porównywanie pola z liczbą 1 zamiast ze znakiem '1'. Każdy wiersz jest ciągiem znaków, więc każde pole jest znakiem.
Odczytywanie sąsiedniego pola przed sprawdzeniem 0 ≤ row < rows i 0 ≤ col < cols. Wtedy pole lądu na krawędzi powoduje odczyt poza mapą.
Implementowanie wypełniania rekurencyjnie. Python domyślnie zatrzymuje się po 1 000 wywołaniach, a w innych językach stos może się przepełnić przy jednej dużej wyspie.
Pobieranie pierwszego elementu listy w Pythonie za pomocą pop(0), co zajmuje czas proporcjonalny do długości listy. Użyj collections.deque i popleft().

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu „Number of Islands”?

O(rows × cols). Skanowanie sprawdza każde pole raz, a każde pole lądu trafia na stos lub do kolejki raz i sprawdza czterech sąsiadów. Oznaczenia odwiedzonych pól oraz stos lub kolejka zajmują O(rows × cols) miejsca na mapie, która w całości składa się z lądu.

Czy w przypadku problemu liczby wysp użyć BFS czy DFS?

Oba rozwiązania są poprawne pod względem czasu i pamięci, ponieważ wystarczy oznaczyć każde pole wyspy. BFS z kolejką nigdy nie używa rekurencji; DFS jest równie bezpieczny, gdy używa jawnego stosu.

Czy potrafisz rozwiązać problem liczby wysp za pomocą struktury union-find?

Tak. Umieść każde pole lądu w osobnym zbiorze i rozpocznij liczenie od liczby pól lądu. Połącz każdą parę sąsiadujących pól lądu i zmniejsz licznik o jeden za każdym razem, gdy połączenie scala dwa różne zbiory. Dzięki kompresji ścieżek czas działania jest zbliżony do O(rows × cols).

Czy potrafisz policzyć wyspy bez osobnej tablicy odwiedzonych pól?

Tak, jeśli możesz zmieniać mapę: zamieniaj każde pole lądu na wodę, gdy tylko do niego dotrzesz. W wielu językach nie można zmieniać ciągów znaków w miejscu, więc najpierw kopiujesz wiersze do siatki znaków, co zajmuje tyle samo miejsca co znaczniki odwiedzonych pól.

def numIslands(grid):
    # Wpisz kod tutaj

Test #1

Test #2

Argument

grid = ["11000", "11000", "00100", "00011"]

Oczekiwany wynik