Swim in Rising Water

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

O(n² log n) z algorytmem Dijkstry: każda z n² komórek jest umieszczana na kopcu i zdejmowana z niego co najwyżej raz. Wyszukiwanie binarne poziomu wody ma taki sam rząd złożoności: około log2(n²) wypełnień obszaru, każde o złożoności O(n²). Oba algorytmy wykorzystują O(n²) pamięci.

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

Tak. To, czy możesz przedostać się na poziomie t , zmienia się raz z false na true przy odpowiedzi. Wyszukiwanie binarne po t , w którym jako testu używa się wypełniania obszaru, wymaga około log2(n²) wypełnień, czyli 14 dla siatki 100 × 100.

Q: Czy struktura 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 zatrzymaj się, gdy tylko oba narożniki znajdą się w tym samym zbiorze. Wysokość ostatniej otwartej komórki jest odpowiedzią. Ponieważ każda wartość od 0 do n²-1 występuje raz, tablica mapująca wysokość na komórkę wyznacza kolejność bez sortowania.

TrudneNajkrótsze ścieżki Kopiec Wyszukiwanie binarne

+10

Dostajesz siatkę n × n wysokości, która zawiera każdą liczbę od 0 do n²-1 dokładnie raz. 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 znajduje się pod wodą. Zaczynasz w komórce w lewym górnym rogu. Możesz bez straty czasu przepłynąć do komórki sąsiadującej z twoją bokiem, jeśli obie znajdują się pod wodą. 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 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 0, 2, 1, a najwyższa komórka to 2. Przez lewą dolną komórkę przebiega przez 0, 3, 1, a najwyższa komórka to 3. W chwili 2 pierwsza trasa jest pod wodą.

Pytanie dodatkowe

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

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Przejście wymaga tyle czasu, ile wynosi wartość jego najwyższej komórki, ponieważ woda musi pokryć każdą komórkę, przez którą przechodzisz. Znajdź więc przejście między narożnikami, którego najwyższa komórka ma najniższą wartość: najkrótszą ścieżkę, której koszt jest maksimum, a nie sumą. Podnoś poziom wody krok po kroku, użyj wyszukiwania binarnego albo uruchom algorytm Dijkstry dla tego kosztu.

Podnoś poziom wody krok po kroku

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

Intuicja

Ustal poziom wody t. Jedno zalanie od lewego górnego rogu, przez komórki o wysokości co najwyżej t, pozwala sprawdzić, czy da się dotrzeć do prawego dolnego rogu. Ustaw początkowo t na wartość większą z wysokości obu narożników, max(grid[0][0], grid[n-1][n-1]), ponieważ oba muszą znaleźć się pod wodą, i zwiększaj je o 1, aż zalanie dotrze do celu. Podnoszenie poziomu wody tylko otwiera kolejne komórki, więc pierwsza wartość, dla której to działa, jest odpowiedzią.

Każde zalanie kosztuje O(n²), a poziom wody może wzrosnąć niemal n² razy: na siatce 100 × 100 nawet do 10^4 poziomów × 10^4 komórek, czyli około 10^8 odwiedzin komórek.

Algorytm

Ustaw t na większą z dwóch wysokości narożników.
Wykonaj wypełnianie zalewowe od lewego górnego rogu przez komórki o wysokości nie większej niż t, używając jawnego stosu i oznaczenia odwiedzenia dla każdej komórki.
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 zalewania nie przechodzi dla każdego poziomu poniżej odpowiedzi i przechodzi dla każdego poziomu od odpowiedzi wzwyż. Wyszukiwanie binarne znajduje tę granicę między wyższym narożnikiem a n²-1, gdzie cała siatka jest pod wodą.

W przykładzie 5 × 5 lo = 6 i hi = 24. Poziom 15 nie przechodzi, więc lo = 16. Poziomy 20, 18, 17 i 16 przechodzą, a wyszukiwanie kończy się na 16 po pięciu zalaniach.

Siatka 100 × 100 ma 10^4 poziomów, więc rozstrzyga to około 14 zalań: około 1.4 × 10^5 odwiedzin komórek zamiast 10^8.

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 wypełnianie obszaru 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

Przypisz każdej trasie koszt równy wysokości jej najwyższego pola. Algorytm Dijkstry nadal działa, ponieważ przedłużenie trasy do pola o wysokości h kosztuje max(old cost, h), czyli nigdy mniej niż dotychczasowy koszt. Utrzymuj kopiec minimum pól, uporządkowany według tego czasu, zaczynając od lewego górnego pola o wartości grid[0][0]. Gdy prawy dolny element opuści kopiec, jego czas będzie odpowiedzią.

Możesz oznaczyć pole jako odwiedzone już przy pierwszym umieszczeniu go w kopcu. Pola opuszczają kopiec w kolejności rosnących czasów, więc pierwsze pole, które dotrze do sąsiada, zapewni mu najmniejszy czas, jaki mogłoby uzyskać dowolne pole, a każde pole trafia do kopca tylko raz.

Kopiec przechowuje krawędź obszaru, do którego możesz dotrzeć, a każde zdjęcie elementu z kopca podnosi poziom wody dokładnie na tyle, by można było tam wejść. W przykładzie 5 × 5 zdjęte elementy mają kolejno wartości 0, 1, 2, 3, 4, 5, a następnie pojawia się brama o wartości 16; prawy dolny element opuszcza kopiec z wartością 16.

Algorytm

Oznacz lewy górny element jako odwiedzony i dodaj go z czasem grid[0][0].
Zdejmij komórkę o najmniejszym czasie t. Jeśli jest to prawy dolny element, zwróć t.
Dla każdego jeszcze nieodwiedzonego sąsiada oznacz go jako odwiedzony 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

Pomijanie wysokości samego narożnika. Odpowiedź wynosi co najmniej grid[0][0] i grid[n-1][n-1]: dla [[3, 0], [1, 2]] wynosi 3.
Chciwe przechodzenie do najniższego sąsiada. Najlepsza trasa może prowadzić pod górę do bramy, a potem okrężną drogą, jak w przykładzie 5 × 5.
Dodawanie wysokości na trasie, 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 obszaru. Kręta trasa może mieć tysiące komórek, co przekracza limit Pythona wynoszący 1 000 zagnieżdżonych wywołań.

Najczęstsze pytania3

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

O(n² log n) z algorytmem Dijkstry: każda z n² komórek jest umieszczana na kopcu i zdejmowana z niego co najwyżej raz. Wyszukiwanie binarne poziomu wody ma taki sam rząd złożoności: około log2(n²) wypełnień obszaru, każde o złożoności O(n²). Oba algorytmy wykorzystują O(n²) pamięci.

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

Tak. To, czy możesz przedostać się na poziomie t, zmienia się raz z false na true przy odpowiedzi. Wyszukiwanie binarne po t, w którym jako testu używa się wypełniania obszaru, wymaga około log2(n²) wypełnień, czyli 14 dla siatki 100 × 100.

Czy struktura 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 zatrzymaj się, gdy tylko oba narożniki znajdą się w tym samym zbiorze. Wysokość ostatniej otwartej komórki jest odpowiedzią. Ponieważ każda wartość od 0 do n²-1 występuje raz, tablica mapująca wysokość na komórkę wyznacza kolejność bez sortowania.

def swimInWater(grid):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

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 pytania3

Podobne zadania