Rotting Oranges

+10

Otrzymujesz siatkę jako listę wierszy o równej długości. Każda komórka ma wartość 0 (pusta), 1 (świeża pomarańcza) lub 2 (zgniła pomarańcza). W każdej minucie każda świeża pomarańcza, która sąsiaduje bokiem ze zgniłą pomarańczą — u góry, na dole, z lewej lub z prawej strony — gnije. Zwróć liczbę minut, po których nie pozostanie żadna świeża pomarańcza, albo -1, jeśli jakaś świeża pomarańcza nigdy nie zgnije. Siatka, w której od początku nie ma świeżych pomarańczy, wymaga 0 minut.

Funkcja

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

gridinteger-2d-array: siatka, jedna lista wartości 0, 1 i 2 w każdym wierszu
Zwracainteger: liczba minut do momentu, gdy żadna pomarańcza nie będzie świeża, lub -1, jeśli to nigdy nie nastąpi

Ograniczenia

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Każdy wiersz ma tę samą długość.
Każdy element grid[i][j] ma wartość 0, 1 lub 2.

Przykłady

Wejście: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Wyjście: 6
Wyjaśnienie: Zapisując komórki jako (wiersz, kolumna), zaraza opuszcza (0,0) i podąża jedyną ścieżką: (0,1) w 1. minucie, (0,2) i (1,1) w 2. minucie, (2,1) w 3. minucie, (2,0) i (2,2) w 4. minucie, (2,3) w 5. minucie. Pomarańcza w (1,3) styka się tylko z (2,3), więc zgnije jako ostatnia, w 6. minucie.

+21 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że każda świeża pomarańcza potrzebuje określonej liczby minut, aby zgnić, gdy zgnije sąsiadująca z nią pomarańcza. Jak w takim razie obliczyć czas zakończenia?

Rozwiązanie

Gnicie zaczyna się jednocześnie od każdej zgniłej pomarańczy i przesuwa się o jedno pole na minutę, więc odpowiedzią jest odległość: ile kroków dzieli najdalszą świeżą pomarańczę od najbliższej zgniłej pomarańczy. Przeszukiwanie wszerz mierzy dokładnie tę odległość, jeśli przed rozpoczęciem umieścisz w kolejce wszystkie zgniłe pomarańcze, a następnie będziesz przetwarzać kolejkę poziom po poziomie, minuta po minucie.

Symuluj minuta po minucie

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

Intuicja

Postępuj zgodnie z treścią zadania. Co minutę przejrzyj całą siatkę i wypisz każdą świeżą pomarańczę, która sąsiaduje ze zgniłą. Następnie zepsuj je wszystkie, zwiększ licznik o jeden i przejrzyj siatkę ponownie. Zatrzymaj się, gdy podczas przeglądania nie znajdziesz niczego do zepsucia. Jeśli w tym momencie w siatce nadal znajduje się świeża pomarańcza, zgnilizna nigdy do niej nie dotrze: zwróć -1.

Najpierw wypisz, potem zepsuj. Jeśli zepsujesz pomarańczę w środku przeglądania, komórka sprawdzona później w tym samym przeglądaniu zobaczy ją jako zgniłą i również się zepsuje, więc zgnilizna rozprzestrzeni się na kilka komórek w ciągu jednej minuty, a licznik będzie zbyt niski.

To poprawne rozwiązanie, ale każda minuta wymaga pełnego przeglądnięcia rows × cols komórek, a liczba minut może zbliżyć się do liczby komórek. Na siatce 150 × 150, na której świeże pomarańcze tworzą jedną krętą ścieżkę, a zgnilizna znajduje się na jej początku, rozprzestrzenienie się zgnilizny zajmuje 11,324 minuty: 11,324 przeglądnięcia po 22,500 komórek, czyli około 2.5 × 10^8 sprawdzeń komórek; prawie wszystkie dotyczą komórek, które nie mogą się zmienić.

Algorytm

Ustaw minuty na 0.
Przeskanuj siatkę i wypisz każdą świeżą pomarańczę, która ma zgniłego sąsiada.
Jeśli lista jest pusta, zatrzymaj się. W przeciwnym razie zamień wszystkie wypisane pomarańcze w zgniłe, dodaj 1 do liczby minut i przeskanuj ponownie.
Zwróć -1, jeśli pozostała świeża pomarańcza, w przeciwnym razie zwróć liczbę minut.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                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 grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

Wiel źródłowe przeszukiwanie wszerz poziomami

Intuicja

Skanowanie marnuje czas na komórki odległe od akcji. Jedyne pomarańcze, które mogą zgnić w minucie t+1, to świeże sąsiadujące z pomarańczami, które zgniły w minucie t. Dlatego umieść w kolejce dokładnie te pomarańcze: granicę rozprzestrzeniania się zgnilizny.

Rozpocznij kolejkę od wszystkich pomarańczy zgniłych w minucie 0, umieszczając je w niej razem. To właśnie część wieloźródłowa. Świeża pomarańcza gnije w minucie równej jej odległości od najbliższej zgniłej pomarańczy, a przeszukiwanie wszerz rozpoczęte ze wszystkich źródeł dociera do każdej komórki najpierw od źródła, które jest najbliżej. Jedno przeszukiwanie wykonuje pracę, którą inaczej trzeba by wykonać osobno dla każdego źródła, a potem wyznaczyć minimum.

Następnie przetwarzaj poziomami. Na początku minuty w kolejce znajduje się k pomarańczy — tych, które zgniły w poprzedniej minucie. Pobierz dokładnie k elementów z początku kolejki; dla każdego z nich spraw, by zgniły jego świeże sąsiadujące pomarańcze, i dodaj je na końcu kolejki. Gdy przetworzysz wszystkie k elementów, mija minuta, a w kolejce znajduje się następna granica. W pierwszym przykładzie poziomy to {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: sześć kroków od początku, czyli sześć minut.

Policz świeże pomarańcze na początku i zmniejszaj tę liczbę za każdym razem, gdy jedna z nich zgnije. Zakończ, gdy liczba osiągnie 0; w przeciwnym razie ostatni poziom dodałby minutę, w której nic nie gnije. Zwróć -1, jeśli kolejka się opróżni, gdy liczba nadal będzie większa od 0. Każda komórka trafia do kolejki najwyżej raz i sprawdza czterech sąsiadów, więc złożoność czasowa wynosi O(rows × cols).

Algorytm

Umieść każdą zgniłą pomarańczę w kolejce i policz świeże pomarańcze.
Ustaw minutes na 0. Dopóki kolejka nie jest pusta i pozostały świeże pomarańcze, zwiększ minutes o 1 i zapamiętaj rozmiar kolejki k.
Wyjmij k pomarańczy z przodu kolejki. Dla każdego świeżego sąsiada w siatce oznacz go jako zgniłego, zmniejsz liczbę świeżych pomarańczy i dodaj go na koniec kolejki.
Gdy pętla się zakończy, zwróć minutes, jeśli liczba świeżych pomarańczy wynosi 0; w przeciwnym razie zwróć -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            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 grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi różni się tutaj o jedną minutę albo wynika z rozpoczęcia wyszukiwania w niewłaściwym miejscu.

Liczenie minuty za ostatni poziom. Jeśli pętla działa, dopóki kolejka nie będzie pusta, jej ostatnia iteracja nie zaraża niczego, a mimo to dodaje 1. Zatrzymaj się, gdy tylko nie zostanie żadna świeża pomarańcza.
Wyszukiwanie kolejno od każdej zgniłej pomarańczy. Pierwsze wyszukiwanie obejmuje każdą osiągniętą pomarańczę, używając własnego zegara, więc dwa źródła, które powinny spotkać się pośrodku, dają zbyt długi czas: [[2, 1, 1, 1, 1, 1, 1, 2]] wymagają 3 minut, a nie 6.
Gnicie pomarańczy podczas skanowania w wersji minuta po minucie. Komórka położona dalej w tym samym skanowaniu widzi je wtedy jako zgniłe, a zaraza przechodzi przez kilka komórek w ciągu jednej minuty.
Zwracanie wartości -1, ponieważ nie ma zgniłej pomarańczy. Jeśli nie ma też świeżej pomarańczy, nic nie musi się wydarzyć: [[0]] zwraca 0. Odpowiedź -1 dotyczy tylko świeżych pomarańczy, które nigdy nie zgniją.
Oznaczanie pomarańczy jako zgniłej przy wyjmowaniu jej z kolejki zamiast przy dodawaniu. Pomarańcza sąsiadująca z dwiema zgniłymi trafia wtedy do kolejki dwukrotnie, a liczba świeżych pomarańczy spada poniżej zera.
Wyszukiwanie w głąb. Podąża jedną ścieżką tak daleko, jak się da, więc moment, w którym po raz pierwszy dociera do pomarańczy, nic nie mówi o minucie, w której ta pomarańcza zgnije.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu gnijących pomarańczy?

O(rows × cols) przy wyszukiwaniu wszerz. Pierwsze skanowanie sprawdza każdą komórkę raz, a każda pomarańcza trafia do kolejki najwyżej raz i sprawdza czterech sąsiadów. W najgorszym przypadku kolejka zajmuje O(rows × cols) miejsca — gdy siatka jest pełna zgniłych pomarańczy.

Dlaczego w problemie „Gnijące pomarańcze” używać BFS, a nie DFS?

Przeszukiwanie wszerz odwiedza komórki w kolejności ich odległości od punktu startowego, a tutaj odległość oznacza czas: poziom k przeszukiwania to dokładnie zbiór pomarańczy, które psują się w minucie k. Przeszukiwanie w głąb może dotrzeć do komórki długą okrężną drogą, zanim znajdzie krótszą trasę, więc musiałoby odwiedzać komórki ponownie za każdym razem, gdy znajdzie krótszą drogę.

Co to jest BFS z wielu źródeł?

Przeszukiwanie wszerz, które rozpoczyna się od kilku komórek w kolejce w odległości 0 zamiast od jednej. W jednym przebiegu wyznacza odległość każdej komórki od najbliższego źródła — taki sam wynik jak przy osobnym przeszukiwaniu dla każdego źródła i wybraniu najmniejszej odległości, ale przy koszcie jednego przeszukiwania. Stosuje się je do każdego pytania o „odległość od najbliższego X” na siatce.

Czy potrafisz rozwiązać zadanie „Gnijące pomarańcze” bez zmieniania siatki?

Tak. Użyj osobnej tablicy odwiedzonych pól i sprawdzaj ją zamiast wpisywać 2 do siatki. Wymaga to dodatkowej pamięci O(rows × cols), której kolejka i tak może potrzebować. W językach, które przekazują siatkę przez referencję, wpisywanie do niej zmienia również siatkę wywołującego, o co osoba prowadząca rozmowę kwalifikacyjną może Cię zapytać.

Python

def orangesRotting(grid):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane