Rat in a Maze

+10

Bir fare, n × n boyutundaki bir maze dizisinin sol üst hücresinden başlar; 1 açık bir hücreyi, 0 ise bir duvarı belirtir ve fare sağ alt hücreye ulaşmalıdır. Her hamle, açık bir hücreye doğru bir hücre aşağı (D), sola (L), sağa (R) veya yukarı (U) gider. Bir yol hiçbir hücreyi iki kez ziyaret etmez ve çıkışta sonlanır.

Her yolu, hamlelerden oluşan bir dize olarak alfabetik sırayla döndür; hiç yol yoksa boş bir dizi döndür.

Fonksiyon

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

mazeinteger-2d-array: n × n ızgara; açık hücre için 1 ve duvar için 0
Döndürürstring-array: sol üstten sağ alta giden her yolu, alfabetik sırayla bir hareket dizisi olarak

Kısıtlar

2 ≤ n ≤ 5
maze[i][j] 0 ya da 1'dir.
Her test labirentinde en fazla 2.000 yol vardır. Açık bir 5 × 5 labirentte 8.512 yol vardır, bu nedenle testlerde yer almaz.

Örnekler

Girdi: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Çıktı: ["RDDRDR", "RDRDDR"]
Açıklama: Başlangıçta yalnızca sağdaki hücre açıktır ve oradan da yalnızca alttaki hücre açıktır; bu yüzden her iki yol da RD ile başlar. RDDRDR önce gelir, çünkü üçüncü hareketi olan D, R'den önce gelir.

Ek soru

Tüm dört hamleye izin verildiğinde, yolları listelemeden sayabilir misin? Sayı hesaplanamaz hâle gelmeden önce n ne kadar büyük olabilir?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her yolu, tekrar ve boşluk olmadan listelemelisin. Geri izleme bunu sağlar: yolu her seferinde bir hamleyle uzat, kullandığı hücreleri engelle ve o hücreden geri çıkarken engeli kaldır. Hamleleri alfabetik sırayla denemek, yolların sıralı çıkmasını sağlar.

Her yolu önce genişlik öncelikli olarak genişlet, sonra sırala

Sezgi

Kısmi yolları; her birinin hücresini, kullandığı hücreleri ve hareketlerini içeren bir kuyrukta tut. Kuyruktan bir yol al ve açık, kullanılmamış bir hücreye yapılan tüm tek hareketlik uzantıları kuyruğa geri koy veya çıkışa ulaşıyorsa yolu kaydet. Her yol tam olarak bir kez bulunur. En fazla 25 hücre olduğunda, kullanılan hücreler kümesi tek bir tamsayıya sığar: r * n + c biti, (r, c) hücresini temsil eder.

Kuyruk, yolları en kısadan başlayarak verir; bu sıralı düzen değildir. Açık bir 5 × 5 labirentte 16 hareketlik DDDDRRRULLURRRDD, 8 hareketlik DDDRDRRR'den önce sıralanır. Bu yüzden en sonda sıralama yaparsın ve kuyruk, kısmi yolların bir katmanını bellekte tutar.

Algoritma

Başlangıç veya çıkış bir duvarsa boş bir dizi döndür.
Başlangıcı kuyruğa ekle: hücre (0, 0), 0 biti ayarlanmış kullanılmış küme, hiç hareket yok.
Sıradaki girdiyi al. Çıkışta duruyorsa hareketlerini kaydet ve devam et.
Aksi takdirde, labirentin içinde açık ve kullanılmamış bir hücreye ulaşan her hareket için o hücreyi, hücrenin biti eklenmiş kullanılmış kümeyi ve sona eklenmiş hareketi içeren bir girdi ekle.
Kuyruk boşaldığında kaydedilen yolları sırala ve döndür.

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

Alfabetik sırada geri izleme

Sezgi

Özyinelemeli bir fonksiyon bir hücrede durur. Çıkışa ulaştığında hamleleri kaydeder. Aksi takdirde, yolun geri dönememesi için hücreyi 0 yapar, açık hücrelere yapılan her hamleyi dener ve hücreyi 1 yapar; çünkü daha sonraki bir yol bu hücreden geçebilir. Bellek, mevcut yoldan ve en fazla n² derinliğindeki bir özyinelemeden oluşur.

İki yol, farklılaştıkları ilk hamleye kadar hamlelerini paylaşır; arama da o noktada alfabetik olarak daha küçük harfin dalını önce tamamlar. Bir yol çıkışta da durur, dolayısıyla hiçbir yol başka bir yolun başlangıcı olmaz. Hamleler D, L, R, U sırasıyla denendiğinde yollar bu nedenle sıralı biçimde kaydedilir.

Algoritma

Başlangıç veya çıkış bir duvarsa boş bir dizi döndür.
backtrack(r, c) yaz. (r, c) çıkışsa mevcut hareketleri kaydet ve döndür.
maze[r][c] değerini 0 olarak ayarla.
Labirentin içindeki açık bir hücreye ulaşan D, L, R, U hareketlerinin her biri için, sırasıyla harfini ekle, özyinelemeli çağrı yap ve harfi kaldır.
maze[r][c] değerini tekrar 1 olarak ayarla. backtrack(0, 0) çağrısını yap ve kaydedilen yolları döndür.

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

Tuzaklar ve uç durumlar

Geri adım attığında bir hücrenin işaretini kaldırmayı unutmak. Hücre engelli kalır, bu yüzden sonraki hiçbir dal içinden geçemez. DDRR ve DDRURD döndüren açık 3 × 3'lük bir labirentte, 12 yolun 2'si.
Başlangıç noktasının veya çıkışın duvar olabileceğini unutmak. İkinci örnekteki gibi çıkışta bir duvar varsa, yanında biten bir yol değil, boş bir yanıt döndürülmelidir.
Hamleleri aşağı, yukarı, sola, sağa sırasıyla denemek. Yol kümesi doğru, ancak sıraları yanlış olur; alfabetik sıra D, L, R, U şeklindedir.

Sıkça sorulan sorular3

Labirentteki Fare algoritmasının zaman karmaşıklığı nedir?

İlk hareketinden sonra bir yolun her hücrede en fazla üç seçeneği vardır ve en fazla n² hücreyi ziyaret eder; dolayısıyla her birini yazmanın maliyeti O(n²) olan O(3^(n²)) kısmi yol vardır. Duvarlar ve kullanılmış hücreler bu sayıyı büyük ölçüde azaltır.

Geri izleme sırasında ziyaret edildi işareti neden kaldırılmalıdır?

İşaret, "daha önce görüldü" değil, "geçerli yol üzerinde" anlamına gelmelidir. İki farklı yol aynı hücreden geçebilir. Arama o hücreden geri döndükten sonra hücre işaretli kalırsa, o hücreden geçen sonraki tüm yollar kaybolur.

Sıçan yalnızca sağa ve aşağı hareket edebiliyorsa ne olur?

Bu durumda hiçbir yol bir hücreyi yeniden ziyaret edemez; dolayısıyla ziyaret işaretlerine gerek yoktur ve her yol tam olarak 2n-2 hamle içerir. Yolları saymak dinamik programlamaya dönüşür: bir hücreye ulaşmanın yolları, üstündeki açık hücreye ulaşma yolları ile solundaki açık hücreye ulaşma yollarının toplamıdır.

def findPaths(maze):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

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

Beklenen Çıktı

["RDDRDR", "RDRDDR"]