Rat in a Maze

+10

Eine Ratte startet in der linken oberen Zelle eines n × n-maze, wobei 1 eine offene Zelle und 0 eine Wand ist, und muss die rechte untere Zelle erreichen. Jeder Zug führt eine Zelle nach unten (D), links (L), rechts (R) oder oben (U) auf eine offene Zelle. Ein Pfad besucht keine Zelle zweimal und endet am Ausgang.

Gib jeden Pfad als Zeichenfolge von Zügen in alphabetischer Reihenfolge zurück oder ein leeres Array, wenn es keinen gibt.

Funktion

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

mazeinteger-2d-array: das n × n-Raster, mit 1 für ein freies Feld und 0 für eine Wand
Gibt zurückstring-array: jeden Pfad von oben links nach unten rechts als Folge von Bewegungen, in alphabetischer Reihenfolge

Einschränkungen

2 ≤ n ≤ 5
maze[i][j] ist 0 oder 1.
Jedes Testlabyrinth hat höchstens 2.000 Wege. Ein offenes 5 × 5-Labyrinth hat 8.512 Wege und ist daher nicht in den Tests enthalten.

Beispiele

Eingabe: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Ausgabe: ["RDDRDR", "RDRDDR"]
Erklärung: Zu Beginn ist nur die Zelle rechts offen, und von dort aus nur die Zelle darunter, daher beginnen beide Pfade mit RD. RDDRDR steht an erster Stelle, weil sein dritter Zug, D, vor R kommt.

Weiterführende Frage

Wenn alle vier Bewegungen erlaubt sind, kannst du die Wege zählen, ohne sie aufzulisten? Wie groß kann n werden, bevor die Anzahl außer Reichweite gerät?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Du musst jeden Pfad ohne Wiederholungen und Lücken auflisten. Backtracking erledigt das: Erweitere den Pfad Zug für Zug, sperre die verwendeten Zellen und entsperre jede Zelle wieder, wenn du aus ihr zurückgehst. Wenn du die Züge in alphabetischer Reihenfolge ausprobierst, werden die Pfade sortiert ausgegeben.

Erweitere jeden Pfad zuerst in der Breite und sortiere anschließend

Idee

Bewahre eine Warteschlange mit Teilpfaden auf, jeweils mit ihrer Zelle, den bereits verwendeten Zellen und ihren Zügen. Nimm einen heraus und füge jede Erweiterung um einen Zug auf eine offene, unbenutzte Zelle wieder hinzu, oder speichere ihn, wenn er den Ausgang erreicht. Jeder Pfad wird genau einmal gefunden. Bei höchstens 25 Zellen passt die Menge der verwendeten Zellen in eine Ganzzahl: Bit r * n + c steht für die Zelle (r, c).

Die Warteschlange gibt zuerst die kürzesten Pfade aus, aber sie sind nicht sortiert. In einem offenen 5 × 5-Labyrinth wird der 16-Züge-Pfad DDDDRRRULLURRRDD vor dem 8-Züge-Pfad DDDRDRRR sortiert. Deshalb sortierst du am Ende, und die Warteschlange hält eine ganze Schicht von Teilpfaden im Speicher.

Algorithmus

Wenn der Start oder der Ausgang eine Wand ist, gib ein leeres Array zurück.
Füge den Start zur Warteschlange hinzu: Zelle (0, 0), verwendete Menge mit Bit 0, keine Züge.
Nimm den nächsten Eintrag. Wenn er sich am Ausgang befindet, speichere seine Züge und fahre fort.
Füge andernfalls für jeden Zug, der auf einer offenen, unbenutzten Zelle innerhalb des Labyrinths landet, einen Eintrag mit dieser Zelle, dem zur verwendeten Menge hinzugefügten Bit der Zelle und dem angehängten Zug hinzu.
Wenn die Warteschlange leer ist, sortiere die gespeicherten Pfade und gib sie zurück.

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

Backtracking in alphabetischer Reihenfolge

Idee

Eine rekursive Funktion steht auf einer Zelle. Am Ziel speichert sie die Bewegungen. Andernfalls setzt sie die Zelle auf 0, damit der Pfad nicht zurückkommen kann, versucht jeden Zug auf eine offene Zelle und setzt die Zelle wieder auf 1, weil ein späterer Pfad durch sie führen kann. Der Speicherbedarf besteht aus dem aktuellen Pfad und einer Rekursionstiefe von höchstens n².

Zwei Pfade teilen ihre Bewegungen bis zum ersten Zug, bei dem sie sich unterscheiden; dort sucht die Suche zuerst den Zweig mit dem alphabetisch kleineren Buchstaben ab. Ein Pfad endet außerdem am Ziel, daher ist kein Pfad der Anfang eines anderen. Wenn die Züge in der Reihenfolge D, L, R, U ausprobiert werden, werden die Pfade daher in sortierter Reihenfolge gespeichert.

Algorithmus

Wenn der Start oder der Ausgang eine Wand ist, gib ein leeres Array zurück.
Schreibe backtrack(r, c). Wenn (r, c) der Ausgang ist, speichere die aktuellen Bewegungen und kehre zurück.
Setze maze[r][c] auf 0.
Führe für jede Bewegung in der Reihenfolge D, L, R, U, die auf einem freien Feld innerhalb des Labyrinths landet, ihren Buchstaben hinzu, rufe die Funktion rekursiv auf und entferne den Buchstaben.
Setze maze[r][c] wieder auf 1. Rufe backtrack(0, 0) auf und gib die gespeicherten Pfade zurück.

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

Stolperfallen und Grenzfälle

Ein Feld beim Zurückgehen nicht wieder freizugeben. Das Feld bleibt blockiert, sodass kein späterer Zweig hindurchführen kann. In einem offenen 3 × 3-Labyrinth liefert das DDRR und DDRURD, 2 der 12 Wege.
Zu vergessen, dass der Start oder das Ziel eine Wand sein kann. Eine Wand am Ziel, wie im zweiten Beispiel, muss eine leere Antwort ergeben und keinen Weg, der daneben endet.
Die Züge in der Reihenfolge unten, oben, links, rechts auszuprobieren. Die Menge der Wege stimmt, aber ihre Reihenfolge nicht; D, L, R, U ist die alphabetische Reihenfolge.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Ratte in einem Labyrinth“?

Nach seinem ersten Zug hat ein Pfad an jeder Zelle höchstens drei Auswahlmöglichkeiten und besucht höchstens n² Zellen. Daher gibt es O(3^(n²)) Teilpfade, für deren Ausgabe jeweils O(n²) Aufwand anfällt. Wände und bereits besuchte Zellen verringern diese Zahl erheblich.

Warum muss die Markierung „besucht“ beim Zurückverfolgen entfernt werden?

Die Markierung muss „auf dem aktuellen Pfad“ bedeuten, nicht „schon einmal gesehen“. Zwei verschiedene Pfade können durch dieselbe Zelle führen. Bleibt eine Zelle markiert, nachdem die Suche aus ihr zurückgegangen ist, geht jeder spätere Pfad durch diese Zelle verloren.

Was ist, wenn sich die Ratte nur nach rechts und nach unten bewegen darf?

Dann kann kein Pfad ein Feld erneut besuchen, sodass du keine Besuchsmarkierungen brauchst, und jeder Pfad hat genau 2n-2 Schritte. Das Zählen der Pfade wird zu dynamischer Programmierung: Die Anzahl der Möglichkeiten, ein Feld zu erreichen, entspricht der Anzahl der Möglichkeiten, die freie Zelle darüber zu erreichen, plus der Anzahl der Möglichkeiten, die freie Zelle links davon zu erreichen.

def findPaths(maze):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe

["RDDRDR", "RDRDDR"]