Rat in a Maze

+10

Un rat commence dans la cellule en haut à gauche d’un n × n maze, où 1 représente une cellule libre et 0 un mur, et doit atteindre la cellule en bas à droite. Chaque déplacement se fait d’une cellule vers le bas (D), la gauche (L), la droite (R) ou le haut (U), vers une cellule libre. Un chemin ne passe jamais deux fois par la même cellule et se termine à la sortie.

Renvoyez tous les chemins sous forme de chaînes de déplacements, par ordre alphabétique, ou un tableau vide s’il n’y en a aucun.

Fonction

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

mazeinteger-2d-array: la grille n × n, avec 1 pour une case libre et 0 pour un mur
Renvoiestring-array: chaque chemin du coin supérieur gauche au coin inférieur droit sous forme d’une chaîne de déplacements, par ordre alphabétique

Contraintes

2 ≤ n ≤ 5
maze[i][j] est 0 ou 1.
Chaque labyrinthe de test comporte au plus 2 000 chemins. Un labyrinthe ouvert de 5 × 5 en comporte 8 512, il ne fait donc pas partie des tests.

Exemples

Entrée: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Sortie: ["RDDRDR", "RDRDDR"]
Explication: Au départ, seule la case à droite est ouverte, et à partir de là, seule la case en dessous l’est ; les deux chemins commencent donc par RD. RDDRDR vient en premier dans l’ordre de tri, car son troisième déplacement, D, vient avant R.

Pour aller plus loin

Avec les quatre déplacements autorisés, peux-tu compter les chemins sans les énumérer ? Jusqu’à quelle valeur n le compte reste-t-il accessible ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Tu dois répertorier chaque chemin, sans répétitions ni omissions. Le retour sur trace permet de faire cela : prolonge le chemin d’un mouvement à la fois, bloque les cellules qu’il emprunte et débloque chaque cellule lorsque tu en sors en revenant sur tes pas. Essayer les mouvements dans l’ordre alphabétique permet d’obtenir les chemins triés.

Développez chaque chemin en largeur d’abord, puis triez

Intuition

Garde une file de chemins partiels, chacun avec sa cellule, ses cellules déjà utilisées et ses déplacements. Retire-en un et ajoute tous ses prolongements d’un déplacement vers une cellule libre et inutilisée, ou sauvegarde-le s’il atteint la sortie. Chaque chemin est trouvé exactement une fois. Avec au plus 25 cellules, l’ensemble des cellules utilisées tient dans un seul entier : le bit r * n + c représente la cellule (r, c).

La file fournit les chemins du plus court au plus long, ce qui ne correspond pas à l’ordre de tri. Dans un labyrinthe ouvert de 5 × 5, le chemin de 16 déplacements DDDDRRRULLURRRDD est trié avant celui de 8 déplacements DDDRDRRR. Il faut donc trier à la fin, et la file conserve toute une couche de chemins partiels en mémoire.

Algorithme

Si le départ ou la sortie est un mur, renvoie un tableau vide.
Place le départ dans la file d’attente : cellule (0, 0), ensemble utilisé avec le bit 0, aucun déplacement.
Prends l’entrée suivante. Si elle se trouve sur la sortie, enregistre ses déplacements et continue.
Sinon, pour chaque déplacement qui aboutit à une cellule libre et non utilisée dans le labyrinthe, ajoute une entrée avec cette cellule, le bit de la cellule ajouté à l’ensemble utilisé et le déplacement ajouté à la fin.
Lorsque la file d’attente est vide, trie les chemins enregistrés et renvoie-les.

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

Retour arrière par ordre alphabétique

Intuition

Une fonction récursive se trouve sur une cellule. À la sortie, elle enregistre les déplacements. Sinon, elle définit la cellule sur 0 afin que le chemin ne puisse pas y revenir, essaie chaque déplacement vers une cellule libre, puis redéfinit la cellule sur 1, car un chemin ultérieur peut la traverser. La mémoire correspond au chemin actuel et la récursion atteint au maximum une profondeur de n².

Deux chemins partagent leurs déplacements jusqu'au premier déplacement où ils diffèrent, et la recherche explore alors d'abord la branche correspondant à la plus petite lettre. Un chemin s'arrête également à la sortie, donc aucun chemin n'est le début d'un autre. Comme les déplacements sont essayés dans l'ordre D, L, R, U, les chemins sont donc enregistrés dans l'ordre lexicographique.

Algorithme

Si le départ ou la sortie est un mur, renvoie un tableau vide.
Écris backtrack(r, c). Si (r, c) est la sortie, enregistre les déplacements actuels et retourne.
Définis maze[r][c] sur 0.
Pour chaque déplacement dans l’ordre D, L, R, U qui mène à une case libre dans le labyrinthe, ajoute sa lettre, lance l’appel récursif, puis retire la lettre.
Redéfinis maze[r][c] sur 1. Appelle backtrack(0, 0) et renvoie les chemins enregistrés.

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

Pièges et cas limites

Ne pas démarquer une case quand tu reviens en arrière. La case reste bloquée, donc aucune branche ultérieure ne peut la traverser. Dans un labyrinthe ouvert de 3 × 3 qui renvoie DDRR et DDRURD, 2 des 12 chemins.
Oublier que la case de départ ou la sortie peut être un mur. Un mur à la sortie, comme dans le deuxième exemple, doit donner une réponse vide, et non un chemin qui se termine juste à côté.
Essayer les déplacements dans l’ordre bas, haut, gauche, droite. L’ensemble des chemins est correct, mais pas leur ordre ; D, L, R, U est l’ordre alphabétique.

Questions fréquentes3

Quelle est la complexité temporelle de Rat in a Maze ?

Après son premier déplacement, un chemin a au plus trois choix à chaque cellule et visite au plus n² cellules ; il y a donc O(3^(n²)) chemins partiels, chacun nécessitant O(n²) pour être écrit. Les murs et les cellules déjà utilisées réduisent considérablement ce nombre.

Pourquoi faut-il retirer la marque de visite lors du retour en arrière ?

La marque doit signifier « sur le chemin actuel », et non « déjà vu ». Deux chemins différents peuvent passer par la même case. Si une case reste marquée après que la recherche en est ressortie, tous les chemins ultérieurs passant par cette case sont perdus.

Et si le rat ne pouvait se déplacer que vers la droite et vers le bas ?

Alors, aucun chemin ne peut repasser par une cellule : tu n’as donc pas besoin de marquer les cellules visitées, et chaque chemin comporte exactement 2n-2 déplacements. Le dénombrement des chemins se fait par programmation dynamique : le nombre de façons d’atteindre une cellule est égal au nombre de façons d’atteindre la cellule ouverte située au-dessus, plus le nombre de façons d’atteindre la cellule ouverte située à sa gauche.

def findPaths(maze):
    # Écrivez le code ici

Test #1

Test #2

Argument

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

Résultat attendu

["RDDRDR", "RDRDDR"]