Swim in Rising Water

Q: Jaka jest złożoność czasowa algorytmu Swim in Rising Water?

O(n² log n) przy użyciu algorytmu Dijkstry: każda z n² komórek jest dodawana i usuwana ze sterty co najwyżej raz, a sterta może zawierać do n² elementów. Wyszukiwanie binarne poziomu wody ma taki sam rząd złożoności: około log2(n²) wypełnień powodziowych, z których każde wymaga O(n²) operacji. Oba rozwiązania zużywają O(n²) pamięci na oznaczenia odwiedzonych komórek oraz stertę lub stos.

Q: Dlaczego algorytm Dijkstry działa, gdy kosztem jest wartość komórki o najwyższym koszcie?

Dijkstra wymaga jednej właściwości: przedłużenie trasy nigdy nie obniża jej kosztu. Tutaj nowy koszt to max(t, height) , który nigdy nie jest mniejszy niż t , więc ta właściwość jest spełniona. Dlatego gdy komórka po raz pierwszy opuszcza kopiec, jej czas jest ostateczny i możesz zakończyć działanie po dotarciu do celu.

Q: Czy problem „Can Swim in Rising Water” można rozwiązać za pomocą wyszukiwania binarnego?

Tak. To, czy możesz się przedostać na poziomie t , jest fałszywe dla każdego poziomu poniżej odpowiedzi i prawdziwe od poziomu odpowiedzi wzwyż. Wyszukiwanie binarne po t , z wypełnianiem obszaru jako testem, znajduje odpowiedź w około log2(n²) testach: 14 dla siatki 100 × 100.

Q: Czy union-find może rozwiązać problem Swim in Rising Water?

Tak. Otwieraj komórki w kolejności rosnącej wysokości, łącz każdą nową komórkę z jej otwartymi sąsiadami i zakończ, gdy tylko lewa górna i prawa dolna komórka znajdą się w tym samym zbiorze. Odpowiedzią jest wysokość komórki, którą otwarto jako ostatnią. Ponieważ siatka zawiera każdą wartość od 0 do n²-1 dokładnie raz, tabela mapująca wysokość na komórkę podaje kolejność otwierania bez sortowania.

TrudneNajkrótsze ścieżki Kopiec Wyszukiwanie binarne

+10

Otrzymujesz siatkę n × n wysokości, zawierającą każdą liczbę od 0 do n²-1 dokładnie raz, w postaci listy wierszy. Deszcz zaczyna padać w chwili 0, a w chwili t woda wszędzie sięga wysokości t, więc każda komórka o wysokości nie większej niż t jest zalana. Zaczynasz w komórce w lewym górnym rogu. Możesz przepłynąć z jednej komórki do komórki sąsiadującej z nią bokiem, jeśli obie są zalane; przepłynięcie nie zajmuje czasu. Zwróć najwcześniejszy moment, w którym możesz znaleźć się w komórce w prawym dolnym rogu.

Funkcja

swimInWater(grid: integer-2d-array) → integer

gridinteger-2d-array: wysokości, jako lista n wierszy zawierających po n liczb
Zwracainteger: najwcześniejszy moment, w którym możesz dotrzeć do komórki w prawym dolnym rogu

Ograniczenia

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
Każda wartość od 0 do n²-1 występuje dokładnie raz.

Przykłady

Wejście: grid = [[0, 2], [3, 1]]
Wyjście: 2
Wyjaśnienie: Przez prawą górną komórkę trasa przebiega przez komórki 0, 2, 1, a najwyższa z nich ma wartość 2. Przez lewą dolną komórkę trasa przebiega przez komórki 0, 3, 1, a najwyższa z nich ma wartość 3. W chwili 2 pierwsza trasa jest pod wodą, więc odpowiedzią jest 2.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jeśli wysokości mogłyby się powtarzać i sięgać 10^9, które z Twoich podejść nadal działałoby bez zmian i po czym przeprowadziłbyś wyszukiwanie binarne?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Czas potrzebny na pokonanie trasy to wysokość jej najwyższej komórki, ponieważ woda musi pokryć każdą komórkę, przez którą przechodzisz. Zadanie polega więc na znalezieniu trasy między narożnikami, której najwyższa komórka jest możliwie najniższa: najkrótszej ścieżki, której koszt stanowi maksimum, a nie suma. Możesz podnosić poziom wody krok po kroku i za każdym razem go testować, zastosować wyszukiwanie binarne poziomu wody z tym samym testem albo uruchomić algorytm Dijkstry, przyjmując wysokość najwyższej komórki za koszt.

Podnoś poziom wody krok po kroku

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

Intuicja

Ustal poziom wody t. Możesz dotrzeć do komórek o wysokości co najwyżej t, które łączą się ze стартem przez takie komórki. Jedno przeszukiwanie flood fill od lewego górnego rogu znajduje te komórki: dodaj komórkę startową, usuń komórkę ze stosu i dodaj każdego nieodwiedzonego sąsiada o wysokości co najwyżej t. Jeśli dolny prawy róg zostanie odwiedzony, poziom t wystarczy.

Odpowiedzią jest najmniejsze t, dla którego flood fill dociera do celu. Nie może być niższe niż wysokość wyższego z rogów, max(grid[0][0], grid[n-1][n-1]), ponieważ oba rogi muszą znaleźć się pod wodą. Zacznij od tego poziomu i zwiększaj go o 1, aż przeszukiwanie się powiedzie. Pierwszy poziom, który działa, jest odpowiedzią, ponieważ podnoszący się poziom wody tylko udostępnia kolejne komórki i nigdy żadnej nie zamyka: poziom, który działa, będzie działał nadal.

Każdy test wymaga O(n²), a poziom wody może wzrosnąć prawie n² razy, zanim przeszukiwanie dotrze do celu. Na siatce 100 × 100 daje to maksymalnie 10^4 poziomów × 10^4 komórek, czyli około 10^8 odwiedzin komórek. W dużych testach rogi mają wartości 0 i 1, a odpowiedzi mieszczą się w przedziale od 4,950 do 9,998, więc przed znalezieniem odpowiedzi wykonywane są tysiące pełnych przeszukiwań flood fill.

Algorytm

Ustaw t na większą z dwóch wysokości narożników.
Wykonaj wypełnianie od lewego górnego rogu przez komórki o wysokości co najwyżej t, używając jawnego stosu i oznaczając każdą odwiedzoną komórkę.
Jeśli wypełnianie dotrze do prawego dolnego rogu, zwróć t.
W przeciwnym razie zwiększ t o 1 i ponownie wykonaj wypełnianie.

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # You cannot finish before the water covers both corners.
    t = max(grid[0][0], grid[n - 1][n - 1])
    # Raise the water one step at a time until a way through opens.
    while not canReach(grid, t):
        t += 1
    return t

Wyszukiwanie binarne poziomu wody

Intuicja

Test z pierwszego podejścia ma użyteczną właściwość. Nie przechodzi dla każdego poziomu poniżej odpowiedzi, a przechodzi dla każdego poziomu równego odpowiedzi lub wyższego. Pytanie z odpowiedzią tak lub nie, która zmienia się tylko raz — z nie na tak — to właśnie taki przypadek, w którym wyszukiwanie binarne znajduje odpowiedź w logarytmicznej liczbie prób.

Szukaj między lo, wyższym narożnikiem, a hi = n²-1, najwyższą komórką, przy którym cała siatka jest pod wodą i test musi przejść. Sprawdź środkowy poziom. Jeśli uda ci się przejść, odpowiedź jest nie większa niż mid, więc ustaw hi = mid; jeśli nie, jest większa niż mid, więc ustaw lo = mid + 1. Gdy obie wartości się spotkają, ten poziom jest odpowiedzią.

W przykładzie z siatką 5 × 5 lo = 6 i hi = 24. Poziom 15 nie przechodzi, ponieważ górny obszar jest odcięty, więc lo = 16. Poziomy 20, 18, 17 i 16 przechodzą, obniżając hi do 16, a wyszukiwanie kończy się na 16 po pięciu wypełnieniach powodziowych.

Siatka 100 × 100 ma 10^4 poziomów, więc około 14 testów wystarczy, by znaleźć odpowiedź; każdy ma złożoność O(n²): to około 1.4 × 10^5 odwiedzonych komórek zamiast 10^8. Wypełnianie powodziowe wykonuj iteracyjnie. Jeden duży test to kręty korytarz o długości około 5,000 komórek, znacznie głębszy niż limit Pythona wynoszący 1,000 zagnieżdżonych wywołań.

Algorytm

Ustaw lo na wysokość wyższego narożnika, a hi na n²-1.
Gdy lo < hi, oblicz mid = (lo + hi) / 2 i zaokrąglij w dół.
Wykonaj zalewanie na poziomie mid. Jeśli dotrze do prawego dolnego rogu, ustaw hi = mid; w przeciwnym razie ustaw lo = mid + 1.
Zwróć lo.

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # The answer lies between the higher corner and the highest cell.
    lo = max(grid[0][0], grid[n - 1][n - 1])
    hi = n * n - 1
    # canReach is false below the answer and true from it on: find the first true.
    while lo < hi:
        mid = (lo + hi) // 2
        if canReach(grid, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Dijkstra na najwyższym polu trasy

Intuicja

Potraktuj siatkę jak graf i przypisz każdej trasie koszt: wysokość jej najwyższego pola, a nie sumę wysokości pól na trasie. Algorytm Dijkstry nadal działa z takim kosztem, ponieważ wydłużenie trasy nigdy nie obniża jej kosztu. Koszt dłuższej trasy to max(old cost, new height), nigdy mniejszy niż dotychczasowy koszt, a to jedyna własność wymagana przez algorytm Dijkstry.

Użyj kopca minimum z polami uporządkowanymi według ich czasu, czyli wysokości najwyższego pola na najlepszej znalezionej do nich trasie. Zacznij od lewego górnego pola z czasem grid[0][0]. Zdejmij pole o najmniejszym czasie t; każdy nieodwiedzony sąsiad otrzymuje czas max(t, its height). Gdy prawe dolne pole zostanie zdjęte z kopca, jego czas jest odpowiedzią.

Pole możesz oznaczyć jako odwiedzone przy pierwszym dodaniu go do kopca. Pola opuszczają kopiec w kolejności według czasu, więc pierwsze pole, które dotrze do sąsiada, ma najmniejszy czas spośród wszystkich pól, które kiedykolwiek do niego dotrą, a czas dotarcia do sąsiada z tego pola jest najlepszy z możliwych. Późniejsza trasa dotrze do niego z czasem co najmniej tak dużym. Dlatego każde pole trafia do kopca tylko raz, ze swoim ostatecznym czasem.

Tak właśnie podnosi się poziom wody, krok po kroku. Kopiec przechowuje granicę obszaru, do którego możesz dotrzeć, a zdjęcie z niego najniższego pola oznacza podniesienie poziomu wody dokładnie na tyle, by można było tam wejść. W przykładzie 5 × 5 pola są zdejmowane w kolejności 0, 1, 2, 3, 4, 5, a następnie bramka na wysokości 16. Potem każde pole na okrężnej trasie otrzymuje czas 16, a prawe dolne pole opuszcza kopiec z czasem 16, zanim zostanie zdjęte jakiekolwiek wyższe pole.

Każde z n² pól jest dodawane i zdejmowane z kopca najwyżej raz, a każda z tych operacji zajmuje O(log n), więc czas działania wynosi O(n² log n), a wyszukiwanie kończy się, gdy tylko cel zostanie zdjęty z kopca.

Algorytm

Oznacz lewy górny jako odwiedzony i dodaj go z czasem grid[0][0].
Zdejmij komórkę z najmniejszym czasem t. Jeśli jest to prawy dolny, zwróć t.
Dla każdego sąsiada, który nie został jeszcze odwiedzony, oznacz go jako odwiedzonego i dodaj go z czasem max(t, its height).
Powtórz od kroku 2.

import heapq


def swimInWater(grid):
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    # (time, row, col): the time is the highest cell on the best path found to that cell.
    heap = [(grid[0][0], 0, 0)]
    while True:
        t, r, c = heapq.heappop(heap)
        # Cells leave the heap in order of time, so this is the earliest you can be here.
        if r == n - 1 and c == n - 1:
            return t
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                # Reached for the first time from the cell with the smallest time:
                # no later route can arrive earlier, so mark it now.
                seen[nr][nc] = True
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z pominięcia jednego z rogów, dodawania kosztów zamiast wybierania maksimum albo zbyt wczesnego zakończenia przeszukiwania.

Pominięcie wysokości pola startowego. Nie możesz znaleźć się w lewym górnym rogu, zanim nie zostanie on zalany, więc odpowiedź wynosi co najmniej grid[0][0]. Dla [[3, 0], [1, 2]] odpowiedź wynosi 3.
Pominięcie wysokości pola docelowego. Prawy dolny róg również musi zostać zalany, więc odpowiedź wynosi co najmniej grid[n-1][n-1].
Chciwe przechodzenie do najniższego sąsiada bieżącego pola. Najlepsza trasa może prowadzić pod górę do przejścia, a potem długą drogą naokoło, jak w przykładzie 5 × 5. Znajduje ją tylko przeszukiwanie całej granicy osiągniętego obszaru.
Dodawanie wysokości wzdłuż trasy, jak w zwykłym problemie najkrótszej ścieżki. Nowy czas to max(t, height), a nie t + height.
Używanie rekurencji do wypełniania zalanego obszaru. Kręta trasa może mieć tysiące pól, co przekracza limit Pythona wynoszący 1 000 zagnieżdżonych wywołań.
Przemieszczanie się po przekątnej. Możesz przepłynąć tylko na pole, które ma wspólny bok z twoim polem.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu Swim in Rising Water?

O(n² log n) przy użyciu algorytmu Dijkstry: każda z n² komórek jest dodawana i usuwana ze sterty co najwyżej raz, a sterta może zawierać do n² elementów. Wyszukiwanie binarne poziomu wody ma taki sam rząd złożoności: około log2(n²) wypełnień powodziowych, z których każde wymaga O(n²) operacji. Oba rozwiązania zużywają O(n²) pamięci na oznaczenia odwiedzonych komórek oraz stertę lub stos.

Dlaczego algorytm Dijkstry działa, gdy kosztem jest wartość komórki o najwyższym koszcie?

Dijkstra wymaga jednej właściwości: przedłużenie trasy nigdy nie obniża jej kosztu. Tutaj nowy koszt to max(t, height), który nigdy nie jest mniejszy niż t, więc ta właściwość jest spełniona. Dlatego gdy komórka po raz pierwszy opuszcza kopiec, jej czas jest ostateczny i możesz zakończyć działanie po dotarciu do celu.

Czy problem „Can Swim in Rising Water” można rozwiązać za pomocą wyszukiwania binarnego?

Tak. To, czy możesz się przedostać na poziomie t, jest fałszywe dla każdego poziomu poniżej odpowiedzi i prawdziwe od poziomu odpowiedzi wzwyż. Wyszukiwanie binarne po t, z wypełnianiem obszaru jako testem, znajduje odpowiedź w około log2(n²) testach: 14 dla siatki 100 × 100.

Czy union-find może rozwiązać problem Swim in Rising Water?

Tak. Otwieraj komórki w kolejności rosnącej wysokości, łącz każdą nową komórkę z jej otwartymi sąsiadami i zakończ, gdy tylko lewa górna i prawa dolna komórka znajdą się w tym samym zbiorze. Odpowiedzią jest wysokość komórki, którą otwarto jako ostatnią. Ponieważ siatka zawiera każdą wartość od 0 do n²-1 dokładnie raz, tabela mapująca wysokość na komórkę podaje kolejność otwierania bez sortowania.

Python

def swimInWater(grid):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

grid = [[0, 2], [3, 1]]

Oczekiwane

Swim in Rising Water

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Podnoś poziom wody krok po kroku

Wyszukiwanie binarne poziomu wody

Dijkstra na najwyższym polu trasy

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania