Rat in a Maze

+10

Szczur zaczyna w lewym górnym polu n × n maze, gdzie 1 oznacza wolne pole, a 0 ścianę, i musi dotrzeć do prawego dolnego pola. Każdy ruch prowadzi o jedno pole w dół (D), w lewo (L), w prawo (R) lub w górę (U), na wolne pole. Ścieżka nigdy nie odwiedza tego samego pola dwukrotnie i kończy się przy wyjściu.

Zwróć każdą ścieżkę jako ciąg ruchów, w kolejności alfabetycznej, lub pustą tablicę, jeśli nie ma żadnej.

Funkcja

findPaths(maze: integer-2d-array) → string-array

mazeinteger-2d-array: siatka n × n, gdzie 1 oznacza wolne pole, a 0 ścianę
Zwracastring-array: każdą ścieżkę od lewego górnego rogu do prawego dolnego jako ciąg ruchów, w kolejności alfabetycznej

Ograniczenia

2 ≤ n ≤ 5
maze[i][j] ma wartość 0 lub 1.
Każdy labirynt testowy ma co najwyżej 2 000 ścieżek. Otwarty labirynt 5 × 5 ma ich 8 512, więc nie występuje w testach.

Przykłady

Wejście: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Wyjście: ["RDDRDR", "RDRDDR"]
Wyjaśnienie: Na początku otwarta jest tylko komórka po prawej, a stamtąd tylko komórka poniżej, więc obie ścieżki zaczynają się od RD. RDDRDR jest pierwsza w kolejności sortowania, ponieważ jej trzeci ruch, D, występuje przed R.

Pytanie dodatkowe

Gdy dozwolone są wszystkie cztery ruchy, czy potrafisz policzyć ścieżki bez ich wypisywania? Jak duże może być n, zanim policzenie ich stanie się poza zasięgiem?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Musisz wypisać każdą ścieżkę, bez powtórzeń i pominięć. Backtracking to umożliwia: wydłużaj ścieżkę po jednym ruchu, blokuj używane przez nią komórki i odblokowuj każdą komórkę, gdy się z niej cofasz. Wypróbowanie ruchów w kolejności alfabetycznej sprawi, że ścieżki będą posortowane.

Rozwijaj każdą ścieżkę wszerz, a następnie sortuj

Intuicja

Przechowuj kolejkę częściowych ścieżek, z których każda zawiera swoją komórkę, użyte komórki i ruchy. Wyjmij jedną ścieżkę i dodaj z powrotem każde jej rozszerzenie o jeden ruch prowadzące do otwartej, nieużytej komórki albo zapisz ją, jeśli dociera do wyjścia. Każda ścieżka zostaje znaleziona dokładnie raz. Przy maksymalnie 25 komórkach zbiór użytych komórek mieści się w jednej liczbie całkowitej: bit r * n + c oznacza komórkę (r, c).

Kolejka zwraca ścieżki najpierw według długości, a nie w kolejności sortowania. W otwartym labiryncie 5 × 5 ścieżka o długości 16 ruchów DDDDRRRULLURRRDD sortuje się przed ścieżką o długości 8 ruchów DDDRDRRR. Dlatego sortujesz na końcu, a kolejka przechowuje w pamięci całą warstwę częściowych ścieżek.

Algorytm

Jeśli start lub wyjście jest ścianą, zwróć pustą tablicę.
Umieść start w kolejce: komórkę (0, 0), zbiór użytych pól z ustawionym bitem 0, bez ruchów.
Pobierz następny wpis. Jeśli znajduje się na wyjściu, zapisz jego ruchy i kontynuuj.
W przeciwnym razie dla każdego ruchu, który prowadzi na otwartą, nieużytą komórkę wewnątrz labiryntu, dodaj wpis zawierający tę komórkę, jej bit dodany do zbioru użytych pól oraz dopisany ruch.
Gdy kolejka będzie pusta, posortuj zapisane ścieżki i zwróć je.

from collections import deque


def findPaths(maze):
    n = len(maze)
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return []
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    result = []
    # Each entry is a path in progress: its cell, the cells it has used
    # (bit r * n + c), and its moves so far.
    queue = deque([(0, 0, 1, "")])
    while queue:
        r, c, used, path = queue.popleft()
        if r == n - 1 and c == n - 1:
            result.append(path)
            continue
        for letter, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                bit = 1 << (nr * n + nc)
                if not used & bit:
                    queue.append((nr, nc, used | bit, path + letter))
    result.sort()  # shorter paths were found first, so sort by text
    return result

Przeszukiwanie z nawrotami w kolejności alfabetycznej

Intuicja

Funkcja rekurencyjna znajduje się na komórce. Przy wyjściu zapisuje ruchy. W przeciwnym razie ustawia komórkę na 0, aby ścieżka nie mogła wrócić, próbuje wykonać każdy ruch na wolną komórkę, a następnie ustawia komórkę z powrotem na 1, ponieważ późniejsza ścieżka może przez nią przechodzić. Pamięcią jest bieżąca ścieżka, a rekurencja ma głębokość co najwyżej n².

Dwie ścieżki mają wspólne ruchy aż do pierwszego ruchu, przy którym się różnią; w tym miejscu wyszukiwanie najpierw kończy gałąź z mniejszą literą. Ścieżka zatrzymuje się również przy wyjściu, więc żadna ścieżka nie jest początkiem innej. Gdy ruchy są wypróbowywane w kolejności D, L, R, U, ścieżki są więc zapisywane w posortowanej kolejności.

Algorytm

Jeśli start lub wyjście znajduje się na ścianie, zwróć pustą tablicę.
Napisz backtrack(r, c). Jeśli (r, c) jest wyjściem, zapisz bieżące ruchy i wróć.
Ustaw maze[r][c] na 0.
Dla każdego ruchu w kolejności D, L, R, U, który prowadzi na otwarte pole wewnątrz labiryntu, dodaj jego literę, wykonaj rekurencyjne wywołanie i usuń literę.
Ustaw ponownie maze[r][c] na 1. Wywołaj backtrack(0, 0) i zwróć zapisane ścieżki.

def findPaths(maze):
    n = len(maze)
    result = []
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return result
    # The moves in alphabetical order, so the paths come out sorted.
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    path = []

    def backtrack(r, c):
        if r == n - 1 and c == n - 1:
            result.append("".join(path))
            return
        maze[r][c] = 0  # block the cell while this path uses it
        for letter, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                path.append(letter)
                backtrack(nr, nc)
                path.pop()
        maze[r][c] = 1  # open it again for the other paths

    backtrack(0, 0)
    return result

Pułapki i przypadki brzegowe

Nieodznaczanie komórki podczas cofania się. Komórka pozostaje zablokowana, więc żadna późniejsza gałąź nie może przez nią przejść. W otwartym labiryncie 3 × 3 zwraca to DDRR i DDRURD, czyli 2 z 12 ścieżek.
Zapominanie, że start lub wyjście może być ścianą. Ściana przy wyjściu, jak w drugim przykładzie, musi dać pustą odpowiedź, a nie ścieżkę kończącą się obok niej.
Próbowanie ruchów w kolejności: w dół, w górę, w lewo, w prawo. Zbiór ścieżek jest poprawny, ale ich kolejność nie; D, L, R, U to kolejność alfabetyczna.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Szczura w labiryncie?

Po pierwszym ruchu ścieżka ma w każdej komórce najwyżej trzy możliwości wyboru i odwiedza najwyżej n² komórek, więc istnieje O(3^(n²)) częściowych ścieżek, z których każda wymaga O(n²) pracy, aby ją zapisać. Ściany i odwiedzone komórki znacznie ograniczają tę liczbę.

Dlaczego podczas cofania należy usunąć oznaczenie odwiedzenia?

Znacznik musi oznaczać „na bieżącej ścieżce”, a nie „odwiedzono wcześniej”. Dwie różne ścieżki mogą przechodzić przez tę samą komórkę. Jeśli komórka pozostanie oznaczona po tym, jak wyszukiwanie się z niej wycofa, każda późniejsza ścieżka przechodząca przez tę komórkę zostanie utracona.

Co jeśli szczur może poruszać się tylko w prawo i w dół?

Wtedy żadna ścieżka nie może ponownie odwiedzić komórki, więc nie potrzebujesz znaczników odwiedzenia, a każda ścieżka składa się dokładnie z 2n-2 ruchów. Liczenie ścieżek staje się programowaniem dynamicznym: liczba sposobów dotarcia do komórki to suma liczby sposobów dotarcia do otwartej komórki powyżej niej i do otwartej komórki po jej lewej stronie.

def findPaths(maze):
    # Wpisz kod tutaj

Test #1

Test #2

Argument

maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]

Oczekiwany wynik

["RDDRDR", "RDRDDR"]