Rat in a Maze

+10

Seekor tikus mulai di sel kiri atas pada maze berukuran n × n, dengan 1 sebagai sel terbuka dan 0 sebagai dinding, dan harus mencapai sel kanan bawah. Setiap langkah berpindah satu sel ke bawah (D), kiri (L), kanan (R), atau atas (U) menuju sel terbuka. Sebuah jalur tidak pernah mengunjungi sel yang sama dua kali dan berakhir di pintu keluar.

Kembalikan setiap jalur sebagai string berisi langkah-langkah, dalam urutan alfabetis, atau array kosong jika tidak ada.

Fungsi

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

mazeinteger-2d-array: kisi-kisi n × n, dengan 1 untuk sel terbuka dan 0 untuk dinding
Mengembalikanstring-array: setiap jalur dari kiri atas ke kanan bawah sebagai string gerakan, dalam urutan alfabetis

Batasan

2 ≤ n ≤ 5
maze[i][j] bernilai 0 atau 1.
Setiap labirin dalam pengujian memiliki paling banyak 2,000 jalur. Labirin terbuka 5 × 5 memiliki 8,512 jalur, jadi labirin itu tidak termasuk dalam pengujian.

Contoh

Input: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Output: ["RDDRDR", "RDRDDR"]
Penjelasan: Sejak awal, hanya sel di sebelah kanan yang terbuka, lalu dari sana hanya sel di bawah yang terbuka, jadi kedua jalur dimulai dengan RD. RDDRDR diurutkan lebih dulu karena gerakan ketiganya, D, berada sebelum R.

Pertanyaan lanjutan

Dengan keempat gerakan diizinkan, bisakah kamu menghitung jalurnya tanpa mencantumkannya satu per satu? Seberapa besar nilai n sebelum jumlahnya tak lagi bisa dihitung?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Kamu harus mencantumkan setiap jalur, tanpa pengulangan dan tanpa ada yang terlewat. Backtracking melakukan itu: perluas jalur satu langkah setiap kali, blokir sel yang digunakan, lalu buka blokir setiap sel saat kamu melangkah mundur keluar darinya. Mencoba gerakan dalam urutan alfabetis membuat jalur tersusun.

Tumbuhkan setiap jalur dengan pencarian melebar terlebih dahulu, lalu urutkan

Intuisi

Simpan antrean jalur parsial, masing-masing dengan sel, sel yang sudah digunakan, dan langkahnya. Ambil satu jalur, lalu masukkan kembali setiap perluasan satu langkah ke sel terbuka yang belum digunakan, atau simpan jalur tersebut jika mencapai pintu keluar. Setiap jalur ditemukan tepat satu kali. Dengan paling banyak 25 sel, himpunan sel yang digunakan muat dalam satu bilangan bulat: bit r * n + c mewakili sel (r, c).

Antrean mengeluarkan jalur terpendek terlebih dahulu, yang bukan urutan terurut. Dalam labirin terbuka 5 × 5, jalur 16 langkah DDDDRRRULLURRRDD diurutkan sebelum jalur 8 langkah DDDRDRRR. Jadi, kamu mengurutkannya di akhir, dan antrean menyimpan satu lapisan penuh jalur parsial di memori.

Algoritma

Jika titik awal atau titik keluar berupa tembok, kembalikan array kosong.
Masukkan titik awal ke dalam antrean: sel (0, 0), set terpakai dengan bit 0, tanpa gerakan.
Ambil entri berikutnya. Jika entri itu berada di titik keluar, simpan gerakannya dan lanjutkan.
Jika tidak, untuk setiap gerakan yang mendarat di sel terbuka dan belum digunakan di dalam labirin, tambahkan entri dengan sel tersebut, bit sel itu ditambahkan ke set terpakai, dan gerakan ditambahkan di akhir.
Ketika antrean kosong, urutkan jalur yang tersimpan lalu kembalikan jalur-jalur tersebut.

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

Backtracking dalam urutan alfabetis

Intuisi

Fungsi rekursif berada di sebuah sel. Di pintu keluar, fungsi ini menyimpan langkah-langkahnya. Jika tidak, fungsi ini menetapkan sel tersebut ke 0 agar jalur tidak bisa kembali ke sana, mencoba setiap langkah menuju sel yang terbuka, lalu menetapkan kembali sel tersebut ke 1, karena jalur berikutnya mungkin melewatinya. Memori yang digunakan adalah jalur saat ini, dan kedalaman rekursi paling banyak n².

Dua jalur memiliki langkah-langkah yang sama hingga langkah pertama yang berbeda, dan pada titik itu pencarian menyelesaikan cabang dengan huruf yang lebih awal terlebih dahulu. Jalur juga berhenti di pintu keluar, jadi tidak ada jalur yang menjadi awal jalur lain. Dengan langkah-langkah yang dicoba dalam urutan D, L, R, U, jalur-jalur tersebut pun disimpan dalam urutan terurut.

Algoritma

Jika titik awal atau titik keluar berupa tembok, kembalikan array kosong.
Tulis backtrack(r, c). Jika (r, c) adalah titik keluar, simpan gerakan saat ini lalu kembalikan.
Atur maze[r][c] menjadi 0.
Untuk setiap gerakan dalam urutan D, L, R, U yang berakhir di sel terbuka di dalam labirin, tambahkan hurufnya, lakukan rekursi, lalu hapus huruf tersebut.
Atur kembali maze[r][c] menjadi 1. Panggil backtrack(0, 0) dan kembalikan jalur yang disimpan.

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

Jebakan dan kasus tepi

Tidak membuka kembali sel saat kamu mundur. Sel itu tetap terhalang, sehingga tidak ada cabang berikutnya yang bisa melewatinya. Pada labirin terbuka berukuran 3 × 3, hasilnya DDRR dan DDRURD, 2 dari 12 jalur.
Lupa bahwa titik awal atau pintu keluar bisa berupa tembok. Tembok di pintu keluar, seperti pada contoh kedua, harus menghasilkan jawaban kosong, bukan jalur yang berakhir di sebelahnya.
Mencoba gerakan dengan urutan bawah, atas, kiri, kanan. Kumpulan jalurnya benar, tetapi urutannya salah. D, L, R, U adalah urutan alfabetisnya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Rat in a Maze?

Setelah langkah pertamanya, jalur memiliki paling banyak tiga pilihan di setiap sel, dan jalur itu mengunjungi paling banyak n² sel, sehingga ada O(3^(n²)) jalur parsial, yang masing-masing membutuhkan biaya O(n²) untuk dituliskan. Dinding dan sel yang sudah digunakan sangat mengurangi jumlah ini.

Mengapa tanda sudah dikunjungi harus dihapus saat melakukan backtracking?

Tanda tersebut harus berarti "berada di jalur saat ini", bukan "pernah dikunjungi". Dua jalur yang berbeda dapat melewati sel yang sama. Jika sebuah sel tetap ditandai setelah pencarian mundur darinya, semua jalur berikutnya yang melewati sel tersebut akan hilang.

Apa yang terjadi jika tikus hanya boleh bergerak ke kanan dan ke bawah?

Dengan begitu, tidak ada jalur yang dapat mengunjungi kembali sebuah sel, jadi kamu tidak memerlukan penanda yang sudah dikunjungi, dan setiap jalur memiliki tepat 2n-2 langkah. Menghitung jalur menjadi pemrograman dinamis: banyaknya cara untuk mencapai sebuah sel adalah jumlah cara untuk mencapai sel terbuka di atasnya dan sel terbuka di sebelah kirinya.

def findPaths(maze):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan

["RDDRDR", "RDRDDR"]