Rat in a Maze

+10

Un ratto parte dalla cella in alto a sinistra di un n × n maze, dove 1 indica una cella libera e 0 un muro, e deve raggiungere la cella in basso a destra. Ogni mossa va di una cella verso il basso (D), a sinistra (L), a destra (R) o verso l'alto (U), entrando in una cella libera. Un percorso non visita mai una cella due volte e termina all'uscita.

Restituisci ogni percorso come una stringa di mosse, in ordine alfabetico, oppure un array vuoto se non ce ne sono.

Funzione

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

mazeinteger-2d-array: la griglia n × n, con 1 per una cella aperta e 0 per un muro
Restituiscestring-array: ogni percorso dall'angolo in alto a sinistra a quello in basso a destra come una stringa di mosse, in ordine alfabetico

Vincoli

2 ≤ n ≤ 5
maze[i][j] è 0 oppure 1.
Ogni labirinto di test ha al massimo 2,000 percorsi. Un labirinto aperto di 5 × 5 ne ha 8,512, quindi non è incluso nei test.

Esempi

Input: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Output: ["RDDRDR", "RDRDDR"]
Spiegazione: All'inizio è aperta solo la cella a destra e, da lì, solo la cella sotto, quindi entrambi i percorsi iniziano con RD. RDDRDR viene prima nell'ordinamento perché la sua terza mossa, D, precede R.

Per approfondire

Con tutte e quattro le mosse consentite, riesci a contare i percorsi senza elencarli? Quanto può diventare grande n prima che il conteggio diventi irraggiungibile?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Devi elencare ogni percorso, senza ripetizioni né omissioni. Il backtracking fa proprio questo: estende il percorso di una mossa alla volta, blocca le celle che usa e sblocca ogni cella quando torni indietro. Provando le mosse in ordine alfabetico, i percorsi risultano ordinati.

Espandi ogni percorso in ampiezza, poi ordina

Intuizione

Conserva una coda di percorsi parziali, ciascuno con la propria cella, le celle già usate e le proprie mosse. Estrai un percorso e reinserisci ogni estensione di una mossa verso una cella aperta e non usata, oppure salvalo se raggiunge l’uscita. Ogni percorso viene trovato esattamente una volta. Con al massimo 25 celle, l’insieme delle celle usate entra in un solo intero: il bit r * n + c rappresenta la cella (r, c).

La coda restituisce prima i percorsi più brevi, ma non in ordine di ordinamento. In un labirinto aperto di 5 × 5, il percorso di 16 mosse DDDDRRRULLURRRDD viene prima, nell’ordinamento, di quello di 8 mosse DDDRDRRR. Quindi ordini alla fine, e la coda conserva in memoria un intero livello di percorsi parziali.

Algoritmo

Se la partenza o l’uscita è un muro, restituisci un array vuoto.
Inserisci la partenza nella coda: cella (0, 0), insieme delle celle visitate con il bit 0 impostato, nessuna mossa.
Prendi la voce successiva. Se si trova sull’uscita, salva le sue mosse e continua.
Altrimenti, per ogni mossa che porta a una cella libera e non visitata all’interno del labirinto, aggiungi una voce con quella cella, il bit della cella aggiunto all’insieme delle celle visitate e la mossa aggiunta in coda.
Quando la coda è vuota, ordina i percorsi salvati e restituiscili.

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 ordine alfabetico

Intuizione

Una funzione ricorsiva si trova su una cella. All'uscita salva le mosse. Altrimenti imposta la cella su 0 in modo che il percorso non possa tornarci, prova ogni mossa verso una cella aperta e reimposta la cella su 1, perché un percorso successivo potrebbe passarci. La memoria è costituita dal percorso corrente e da una ricorsione profonda al massimo n².

Due percorsi condividono le mosse fino alla prima mossa in cui differiscono; a quel punto la ricerca completa per prima la diramazione con la lettera più piccola. Inoltre, un percorso si ferma all'uscita, quindi nessun percorso è l'inizio di un altro. Provando le mosse nell'ordine D, L, R, U, i percorsi vengono quindi salvati in ordine ordinato.

Algoritmo

Se la partenza o l'uscita è un muro, restituisci un array vuoto.
Scrivi backtrack(r, c). Se (r, c) è l'uscita, salva le mosse correnti e restituisci.
Imposta maze[r][c] a 0.
Per ogni mossa nell'ordine D, L, R, U che porta a una cella libera all'interno del labirinto, aggiungi la sua lettera, richiama ricorsivamente la funzione e rimuovi la lettera.
Reimposta maze[r][c] a 1. Chiama backtrack(0, 0) e restituisci i percorsi salvati.

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

Trappole e casi limite

Non deselezionare una cella quando torni indietro. La cella rimane bloccata, quindi nessun ramo successivo può attraversarla. In un labirinto aperto 3 × 3 restituisce DDRR e DDRURD, 2 dei 12 percorsi.
Dimenticare che la partenza o l’uscita possono essere un muro. Un muro all’uscita, come nel secondo esempio, deve dare una risposta vuota, non un percorso che termina accanto a essa.
Provare le mosse nell’ordine giù, su, sinistra, destra. L’insieme dei percorsi è corretto, ma il loro ordine no; D, L, R, U è quello alfabetico.

Domande frequenti3

Qual è la complessità temporale di Rat in a Maze?

Dopo la prima mossa, un percorso ha al massimo tre scelte in ogni cella e visita al massimo n² celle, quindi ci sono O(3^(n²)) percorsi parziali, ciascuno dei quali richiede O(n²) per essere scritto. I muri e le celle già usate riducono notevolmente questo numero.

Perché è necessario rimuovere il segno di visitato durante il backtracking?

Il contrassegno deve significare «sul percorso attuale», non «già visitata». Due percorsi diversi possono passare per la stessa cella. Se una cella rimane contrassegnata dopo che la ricerca torna indietro da essa, tutti i percorsi successivi che passano per quella cella vengono persi.

Che cosa succede se il ratto può muoversi solo a destra e in basso?

Quindi nessun percorso può tornare su una cella, perciò non servono segni per le celle visitate e ogni percorso ha esattamente 2n-2 mosse. Il conteggio dei percorsi diventa programmazione dinamica: i modi per raggiungere una cella sono i modi per raggiungere la cella libera sopra di essa più i modi per raggiungere la cella libera alla sua sinistra.

def findPaths(maze):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

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

Output atteso

["RDDRDR", "RDRDDR"]