Rat in a Maze

+10

Um rato começa na célula superior esquerda de um n × n maze, onde 1 é uma célula livre e 0 uma parede, e deve chegar à célula inferior direita. Cada movimento avança uma célula para baixo (D), para a esquerda (L), para a direita (R) ou para cima (U), entrando em uma célula livre. Um caminho nunca visita uma célula duas vezes e termina na saída.

Retorne todos os caminhos como strings de movimentos, em ordem alfabética, ou um array vazio se não houver nenhum.

Função

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

mazeinteger-2d-array: a grade n × n, com 1 para uma célula aberta e 0 para uma parede
Retornastring-array: cada caminho do canto superior esquerdo ao canto inferior direito como uma sequência de movimentos, em ordem alfabética

Restrições

2 ≤ n ≤ 5
maze[i][j] é 0 ou 1.
Cada labirinto de teste tem no máximo 2.000 caminhos. Um labirinto aberto de 5 × 5 tem 8.512, então não está nos testes.

Exemplos

Entrada: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Saída: ["RDDRDR", "RDRDDR"]
Explicação: No início, apenas a célula à direita está aberta e, a partir dela, apenas a célula abaixo, então os dois caminhos começam com RD. RDDRDR vem primeiro na ordenação porque seu terceiro movimento, D, vem antes de R.

Para ir além

Com os quatro movimentos permitidos, você consegue contar os caminhos sem listá-los? Até que valor n pode chegar antes que a contagem fique fora de alcance?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Você precisa listar todos os caminhos, sem repetições nem lacunas. A busca com retrocesso faz isso: estenda o caminho um movimento de cada vez, bloqueie as células que ele usa e desbloqueie cada célula ao sair dela. Tentar os movimentos em ordem alfabética faz com que os caminhos fiquem ordenados.

Expanda todos os caminhos em largura primeiro e, em seguida, ordene.

Intuição

Mantenha uma fila de caminhos parciais, cada um com sua célula, suas células já visitadas e seus movimentos. Retire um caminho da fila e coloque de volta cada extensão de um movimento para uma célula aberta e não visitada, ou salve-o se chegar à saída. Cada caminho é encontrado exatamente uma vez. Com no máximo 25 células, o conjunto de células visitadas cabe em um único inteiro: o bit r * n + c representa a célula (r, c).

A fila entrega primeiro os caminhos mais curtos, o que não é uma ordem classificada. Em um labirinto aberto de 5 × 5, o caminho de 16 movimentos DDDDRRRULLURRRDD é classificado antes do caminho de 8 movimentos DDDRDRRR. Portanto, você classifica no final, e a fila mantém uma camada inteira de caminhos parciais na memória.

Algoritmo

Se o início ou a saída for uma parede, retorne um array vazio.
Coloque o início na fila: célula (0, 0), conjunto de células usadas com o bit 0, sem movimentos.
Retire a próxima entrada. Se ela estiver na saída, salve seus movimentos e continue.
Caso contrário, para cada movimento que levar a uma célula aberta e não utilizada dentro do labirinto, adicione uma entrada com essa célula, o bit da célula adicionado ao conjunto de células usadas e o movimento acrescentado.
Quando a fila estiver vazia, ordene os caminhos salvos e retorne-os.

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

Retrocesso em ordem alfabética

Intuição

Uma função recursiva está em uma célula. Na saída, ela salva os movimentos. Caso contrário, define a célula como 0 para que o caminho não possa voltar, tenta cada movimento para uma célula aberta e define a célula novamente como 1, porque um caminho posterior pode passar por ela. A memória consiste no caminho atual e em uma recursão com profundidade máxima de n².

Dois caminhos compartilham seus movimentos até o primeiro movimento em que diferem; nesse ponto, a busca conclui primeiro o ramo da letra menor. Um caminho também para na saída, portanto nenhum caminho é o início de outro. Com os movimentos tentados na ordem D, L, R, U, os caminhos são, portanto, salvos em ordem classificada.

Algoritmo

Se o início ou a saída for uma parede, retorne um array vazio.
Escreva backtrack(r, c). Se (r, c) for a saída, salve os movimentos atuais e retorne.
Defina maze[r][c] como 0.
Para cada movimento na ordem D, L, R, U que leve a uma célula livre dentro do labirinto, acrescente sua letra, faça a chamada recursiva e remova a letra.
Defina maze[r][c] novamente como 1. Chame backtrack(0, 0) e retorne os caminhos salvos.

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

Armadilhas e casos extremos

Não desmarcar uma célula ao recuar. A célula permanece bloqueada, então nenhum ramo posterior pode passar por ela. Em um labirinto aberto de 3 × 3, isso retorna DDRR e DDRURD, 2 dos 12 caminhos.
Esquecer que a célula inicial ou a saída pode ser uma parede. Uma parede na saída, como no segundo exemplo, deve resultar em uma resposta vazia, não em um caminho que termina ao lado dela.
Tentar os movimentos na ordem baixo, cima, esquerda, direita. O conjunto de caminhos está correto, mas a ordem não; D, L, R, U é a ordem alfabética.

Perguntas frequentes3

Qual é a complexidade de tempo de Rat in a Maze?

Após seu primeiro movimento, um caminho tem no máximo três opções em cada célula e visita no máximo n² células, portanto há O(3^(n²)) caminhos parciais, cada um com custo de O(n²) para ser escrito. Paredes e células já usadas reduzem bastante esse número.

Por que a marca de visitado precisa ser removida ao retroceder?

A marca precisa significar "no caminho atual", não "já visto". Dois caminhos diferentes podem passar pela mesma célula. Se uma célula continuar marcada depois que a busca voltar atrás, todos os caminhos posteriores que passarem por ela serão perdidos.

E se o rato só puder se mover para a direita e para baixo?

Então, nenhum caminho pode revisitar uma célula, portanto você não precisa de marcações de visitado, e todo caminho tem exatamente 2n-2 movimentos. Contar os caminhos se torna programação dinâmica: as maneiras de chegar a uma célula são as maneiras de chegar à célula aberta acima dela mais as maneiras de chegar à célula aberta à sua esquerda.

def findPaths(maze):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

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

Saída Esperada

["RDDRDR", "RDRDDR"]