Rat in a Maze

+10

Una rata comienza en la celda superior izquierda de un n × n maze, donde 1 es una celda abierta y 0 una pared, y debe llegar a la celda inferior derecha. Cada movimiento avanza una celda hacia abajo (D), hacia la izquierda (L), hacia la derecha (R) o hacia arriba (U) hasta una celda abierta. Un camino nunca visita una celda dos veces y termina en la salida.

Devuelve todos los caminos como cadenas de movimientos, en orden alfabético, o un arreglo vacío si no hay ninguno.

Función

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

mazeinteger-2d-array: la cuadrícula n × n, con 1 para una celda abierta y 0 para una pared
Devuelvestring-array: cada ruta desde la esquina superior izquierda hasta la esquina inferior derecha como una cadena de movimientos, en orden alfabético

Restricciones

2 ≤ n ≤ 5
maze[i][j] es 0 o 1.
Cada laberinto de prueba tiene como máximo 2,000 caminos. Un laberinto abierto de 5 × 5 tiene 8,512, así que no está en las pruebas.

Ejemplos

Entrada: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Salida: ["RDDRDR", "RDRDDR"]
Explicación: Al principio solo está abierta la celda de la derecha y, desde allí, solo la celda de abajo, así que ambos caminos comienzan con RD. RDDRDR va primero en el orden porque su tercer movimiento, D, va antes que R.

Para ir más allá

Con los cuatro movimientos permitidos, ¿puedes contar los caminos sin enumerarlos? ¿Qué tan grande puede ser n antes de que el recuento sea inalcanzable?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Debes enumerar todos los caminos, sin repeticiones ni omisiones. El retroceso lo consigue: extiende el camino un movimiento a la vez, bloquea las celdas que utiliza y desbloquea cada celda cuando retrocedes y sales de ella. Probar los movimientos en orden alfabético hace que los caminos queden ordenados.

Expande cada ruta primero en anchura y después ordénalas

Intuición

Mantén una cola de rutas parciales, cada una con su celda, sus celdas usadas y sus movimientos. Saca una y vuelve a añadir todas las extensiones de un movimiento hacia una celda abierta y no usada, o guárdala si llega a la salida. Cada ruta se encuentra exactamente una vez. Con como máximo 25 celdas, el conjunto de celdas usadas cabe en un entero: el bit r * n + c representa la celda (r, c).

La cola entrega primero las rutas más cortas, lo cual no es un orden lexicográfico. En un laberinto abierto de 5 × 5, la ruta de 16 movimientos DDDDRRRULLURRRDD se ordena antes que la ruta de 8 movimientos DDDRDRRR. Así que ordenas al final, y la cola mantiene en memoria toda una capa de rutas parciales.

Algoritmo

Si el inicio o la salida es una pared, devuelve un array vacío.
Pon el inicio en la cola: celda (0, 0), conjunto de celdas usadas con el bit 0, sin movimientos.
Toma la siguiente entrada. Si está en la salida, guarda sus movimientos y continúa.
De lo contrario, para cada movimiento que llegue a una celda abierta y no usada dentro del laberinto, añade una entrada con esa celda, el bit de la celda añadido al conjunto de celdas usadas y el movimiento agregado.
Cuando la cola esté vacía, ordena los caminos guardados y devuélvelos.

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

Retroceso en orden alfabético

Intuición

Una función recursiva se encuentra en una celda. En la salida guarda los movimientos. De lo contrario, establece la celda en 0 para que el camino no pueda volver, prueba cada movimiento hacia una celda abierta y establece la celda de nuevo en 1, porque un camino posterior podría pasar por ella. La memoria es el camino actual y una recursión de como máximo n² niveles de profundidad.

Dos caminos comparten sus movimientos hasta el primer movimiento en el que difieren, y allí la búsqueda termina primero la rama de la letra menor. Un camino también se detiene en la salida, así que ningún camino es el inicio de otro. Con los movimientos probados en el orden D, L, R, U, los caminos se guardan, por lo tanto, en orden lexicográfico.

Algoritmo

Si el inicio o la salida es una pared, devuelve un array vacío.
Escribe backtrack(r, c). Si (r, c) es la salida, guarda los movimientos actuales y devuelve.
Establece maze[r][c] en 0.
Para cada movimiento en el orden D, L, R, U que llegue a una celda abierta dentro del laberinto, añade su letra, realiza la llamada recursiva y elimina la letra.
Vuelve a establecer maze[r][c] en 1. Llama a backtrack(0, 0) y devuelve las rutas guardadas.

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

Errores comunes y casos límite

No desmarcar una celda al retroceder. La celda permanece bloqueada, así que ninguna rama posterior puede atravesarla. En un laberinto abierto de 3 × 3 que devuelve DDRR y DDRURD, 2 de los 12 caminos.
Olvidar que el inicio o la salida pueden ser una pared. Una pared en la salida, como en el segundo ejemplo, debe dar una respuesta vacía, no un camino que termine junto a ella.
Probar los movimientos en el orden abajo, arriba, izquierda, derecha. El conjunto de caminos es correcto, pero su orden no; D, L, R, U es el orden alfabético.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Rat in a Maze?

Después de su primer movimiento, una ruta tiene como máximo tres opciones en cada celda y visita como máximo n² celdas, por lo que hay O(3^(n²)) rutas parciales, cada una con un costo de O(n²) para escribirla. Las paredes y las celdas ya usadas reducen muchísimo esta cantidad.

¿Por qué hay que quitar la marca de visitado al retroceder?

La marca debe significar «en el camino actual», no «visitado antes». Dos caminos distintos pueden pasar por la misma celda. Si una celda sigue marcada después de que la búsqueda retrocede desde ella, se pierden todos los caminos posteriores que pasan por esa celda.

¿Y si la rata solo puede moverse hacia la derecha y hacia abajo?

Después, ningún camino puede volver a visitar una celda, así que no necesitas marcar las celdas visitadas, y cada camino tiene exactamente 2n-2 movimientos. Contar los caminos se convierte en programación dinámica: las formas de llegar a una celda son las formas de llegar a la celda abierta que está encima más las formas de llegar a la celda abierta que está a su izquierda.

def findPaths(maze):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

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

Salida Esperada

["RDDRDR", "RDRDDR"]