Rat in a Maze

+10

Крыса начинает в верхней левой клетке n × n maze, где 1 обозначает свободную клетку, а 0 — стену, и должна добраться до нижней правой клетки. Каждый ход перемещает её на одну клетку вниз (D), влево (L), вправо (R) или вверх (U), на свободную клетку. Путь не проходит через одну клетку дважды и заканчивается у выхода.

Верни все пути в виде строк ходов в алфавитном порядке или пустой массив, если путей нет.

Функция

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

mazeinteger-2d-array: сетка n × n, где 1 обозначает открытую ячейку, а 0 — стену
Возвращаетstring-array: все пути из верхнего левого угла в нижний правый в виде строки ходов, в алфавитном порядке

Ограничения

2 ≤ n ≤ 5
maze[i][j] равно 0 или 1.
В каждом тестовом лабиринте не более 2 000 путей. В открытом лабиринте 5 × 5 их 8 512, поэтому он не входит в тесты.

Примеры

Ввод: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Вывод: ["RDDRDR", "RDRDDR"]
Пояснение: В начале открыта только ячейка справа, а оттуда — только ячейка снизу, поэтому оба пути начинаются с RD. RDDRDR идет первым в сортировке, потому что его третий ход, D, идет перед R.

Дополнительный вопрос

Если разрешены все четыре хода, сможешь ли ты посчитать пути, не перечисляя их? Насколько большим может стать n, прежде чем число путей станет слишком большим?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Нужно перечислить каждый путь, без повторов и пропусков. Для этого подходит поиск с возвратом: продлевайте путь на один ход за раз, блокируйте используемые им клетки и разблокируйте каждую клетку, когда возвращаетесь из неё. Если пробовать ходы в алфавитном порядке, пути будут расположены по порядку.

Расширяйте каждый путь в ширину, затем сортируйте

Идея

Храни очередь частичных путей, каждый из которых содержит свою клетку, использованные клетки и свои ходы. Извлеки один путь и добавь обратно все его расширения на один ход, ведущие в открытую, ещё не использованную клетку, или сохрани его, если он достигает выхода. Каждый путь находится ровно один раз. При не более чем 25 клетках множество использованных клеток помещается в одно целое число: бит r * n + c обозначает клетку (r, c).

Очередь выдаёт сначала самые короткие пути, но порядок не отсортирован. В открытом лабиринте 5 × 5 путь из 16 ходов DDDDRRRULLURRRDD располагается перед путём из 8 ходов DDDRDRRR. Поэтому сортируй в конце, а очередь хранит в памяти целый слой частичных путей.

Алгоритм

Если старт или выход — стена, верни пустой массив.
Помести старт в очередь: ячейка (0, 0), множество использованных ячеек с битом 0, без ходов.
Возьми следующую запись. Если она находится на выходе, сохрани её ходы и продолжай.
Иначе для каждого хода, который ведёт в открытую, ещё не использованную ячейку внутри лабиринта, добавь запись с этой ячейкой, её битом, добавленным в множество использованных ячеек, и добавленным ходом.
Когда очередь опустеет, отсортируй сохранённые пути и верни их.

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

Возврат с перебором в алфавитном порядке

Идея

Рекурсивная функция находится в ячейке. У выхода она сохраняет ходы. В противном случае она устанавливает значение ячейки в 0, чтобы путь не мог вернуться, пробует каждый ход в свободную ячейку и устанавливает значение ячейки обратно в 1, потому что более поздний путь может проходить через неё. Память занимает текущий путь, а глубина рекурсии составляет не более n².

Два пути имеют общие ходы до первого хода, в котором они различаются, и там поиск сначала завершает ветвь с меньшей буквой. Путь также заканчивается у выхода, поэтому ни один путь не является началом другого. Поэтому, если пробовать ходы в порядке D, L, R, U, пути сохраняются в отсортированном порядке.

Алгоритм

Если старт или выход — стена, верни пустой массив.
Напиши backtrack(r, c). Если (r, c) — выход, сохрани текущие ходы и вернись.
Установи maze[r][c] в 0.
Для каждого хода в порядке D, L, R, U, который ведёт в открытую ячейку внутри лабиринта, добавь его букву, вызови функцию рекурсивно и удали букву.
Установи maze[r][c] обратно в 1. Вызови backtrack(0, 0) и верни сохранённые пути.

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

Ловушки и крайние случаи

Не снимая отметку с клетки при возврате. Клетка остаётся заблокированной, поэтому ни одна последующая ветвь не сможет пройти через неё. В открытом лабиринте 3 × 3, который возвращает DDRR и DDRURD, это 2 из 12 путей.
Забывая, что стартовая клетка или выход могут быть стеной. Стена у выхода, как во втором примере, должна давать пустой ответ, а не путь, который заканчивается рядом с ней.
Пробуя ходы в порядке: вниз, вверх, влево, вправо. Набор путей правильный, но порядок — нет; D, L, R, U — это алфавитный порядок.

Частые вопросы3

Какова временная сложность задачи «Крыса в лабиринте»?

После первого хода у пути есть не более трёх вариантов в каждой клетке, и он посещает не более n² клеток, поэтому существует O(3^(n²)) частичных путей, на запись каждого из которых уходит O(n²). Стены и уже посещённые клетки значительно сокращают их количество.

Почему при возврате назад нужно удалять отметку о посещении?

Отметка должна означать «на текущем пути», а не «уже посещена». Два разных пути могут проходить через одну и ту же клетку. Если клетка остаётся отмеченной после того, как поиск возвращается из неё, все последующие пути через эту клетку будут потеряны.

Что, если крыса может двигаться только вправо и вниз?

Тогда ни один путь не может повторно посетить клетку, поэтому отметки посещения не нужны, и каждый путь содержит ровно 2n-2 ходов. Подсчёт путей сводится к динамическому программированию: количество способов добраться до клетки равно сумме количества способов добраться до свободной клетки над ней и количества способов добраться до свободной клетки слева от неё.

def findPaths(maze):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

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

Ожидаемый вывод

["RDDRDR", "RDRDDR"]