Rotting Oranges

+10

Kamu mendapatkan grid berupa list baris dengan panjang yang sama. Setiap sel bernilai 0 (kosong), 1 (jeruk segar), atau 2 (jeruk busuk). Setiap menit, setiap jeruk segar yang berbagi sisi dengan jeruk busuk, di atas, di bawah, di kiri, atau di kanan, akan menjadi busuk. Kembalikan jumlah menit hingga tidak ada jeruk segar yang tersisa, atau -1 jika ada jeruk segar yang tidak akan pernah membusuk. Grid yang tidak memiliki jeruk segar sejak awal membutuhkan waktu 0 menit.

Fungsi

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: grid, satu list berisi 0, 1, dan 2 untuk setiap baris
Mengembalikaninteger: jumlah menit hingga tidak ada jeruk yang segar, atau -1 jika hal itu tidak pernah terjadi

Batasan

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Setiap baris memiliki panjang yang sama.
Setiap grid[i][j] bernilai 0, 1 atau 2.

Contoh

Input: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Output: 6
Penjelasan: Sel adalah (baris, kolom). Pembusukan mengikuti satu-satunya jalur dari (0,0) dan mencapai (2,3) pada menit ke-5. Jeruk di (1,3) hanya bersentuhan dengan (2,3), jadi jeruk itu membusuk paling akhir, pada menit ke-6.

Pertanyaan lanjutan

Misalkan setiap jeruk segar membutuhkan jumlah menit yang berbeda untuk membusuk setelah jeruk di sebelahnya membusuk. Bagaimana kamu menemukan waktu selesainya?

Solusi

Pembusukan menyebar dari semua jeruk busuk secara bersamaan, satu sel per menit, jadi jawabannya adalah jarak: seberapa jauh jeruk segar yang paling jauh dari jeruk busuk terdekat. Pencarian melebar mengukur jarak itu ketika semua jeruk busuk dimasukkan ke dalam antrean dan setiap tingkat antrean mewakili satu menit.

Simulasikan menit demi menit

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Setiap menit, pindai seluruh grid dan catat setiap jeruk segar yang bersentuhan dengan jeruk busuk. Lalu busukkan semuanya dan tambahkan satu ke penghitung waktu. Berhenti saat pemindaian tidak menemukan jeruk yang bisa dibusukkan. Jika masih ada jeruk segar, kembalikan -1.

Catat dulu, busukkan setelahnya. Jika kamu membusukkan jeruk di tengah pemindaian, sel yang diperiksa kemudian dalam pemindaian yang sama akan melihatnya sebagai jeruk busuk, sehingga pembusukan menyebar melewati beberapa sel dalam satu menit.

Setiap menit, pemindaian memeriksa semua sel dalam baris × kolom, dan jumlah menitnya bisa mendekati jumlah sel: jalur berliku pada grid 150 × 150 membutuhkan 11,324 menit, sekitar 2.5 × 10^8 pemeriksaan sel.

Algoritma

Atur menit menjadi 0.
Pindai kisi dan catat setiap jeruk segar yang memiliki jeruk busuk di sebelahnya.
Jika daftarnya kosong, berhenti. Jika tidak, ubah semua jeruk yang tercatat menjadi busuk, tambahkan 1 ke menit, lalu pindai lagi.
Kembalikan -1 jika masih ada jeruk segar, jika tidak, kembalikan menit.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

BFS multi-sumber berdasarkan level

Intuisi

Satu-satunya jeruk yang dapat membusuk pada menit t+1 adalah jeruk segar yang bertetangga dengan jeruk yang membusuk pada menit t, jadi simpan hanya jeruk-jeruk itu dalam antrean. Isi antrean dengan setiap jeruk yang sudah busuk pada menit 0. Jeruk segar membusuk pada menit yang sama dengan jaraknya dari jeruk busuk terdekat, dan pencarian breadth-first yang dimulai dari semua sumber akan mencapai setiap sel pertama kali dari sumber yang paling dekat.

Proses per tingkat. Pada awal suatu menit, antrean berisi jeruk yang membusuk pada menit sebelumnya. Ambil tepat sebanyak itu dari bagian depan, busukkan tetangga-tetangganya yang masih segar, lalu tambahkan ke bagian belakang. Sisanya menjadi frontier berikutnya.

Hitung dahulu jumlah jeruk segar, lalu berhenti saat jumlahnya mencapai 0, atau saat tingkat terakhir menambahkan satu menit tanpa ada jeruk yang membusuk. Setiap sel masuk ke antrean paling banyak satu kali: O(rows × cols).

Algoritma

Masukkan setiap jeruk busuk ke dalam antrean dan hitung jumlah jeruk segar.
Atur menit ke 0. Selama antrean tidak kosong dan masih ada jeruk segar, tambahkan 1 ke menit dan catat ukuran antrean k.
Ambil k jeruk dari bagian depan. Untuk setiap jeruk segar di sebelahnya yang masih berada di dalam grid, tandai sebagai busuk, kurangi jumlah jeruk segar, lalu tambahkan jeruk itu ke bagian belakang.
Saat perulangan berakhir, kembalikan menit jika jumlah jeruk segar adalah 0, jika tidak, kembalikan -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Jebakan dan kasus tepi

Menghitung satu menit untuk level terakhir. Jika perulangan berjalan sampai antrean kosong, putaran terakhirnya tidak membusukkan apa pun, tetapi tetap menambahkan 1. Berhenti segera setelah tidak ada jeruk segar yang tersisa.
Melakukan pencarian dari setiap jeruk busuk secara bergiliran. Pencarian pertama mengklaim setiap jeruk yang dijangkaunya dengan penghitung waktunya sendiri: [[2, 1, 1, 1, 1, 1, 1, 2]] lalu menghasilkan 6 menit, bukan 3.
Mengembalikan -1 karena tidak ada jeruk busuk. Jika tidak ada jeruk segar juga, tidak ada yang perlu terjadi: [[0]] menghasilkan 0.
Menandai jeruk sebagai busuk saat dikeluarkan dari antrean, bukan saat dimasukkan. Jeruk yang berada di sebelah dua jeruk busuk kemudian masuk dua kali, dan jumlah jeruk segar turun di bawah nol.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Rotting Oranges?

O(rows × cols) dengan breadth first search: pemindaian pertama membaca setiap sel satu kali, dan setiap sel oranye masuk ke antrean paling banyak satu kali serta memeriksa empat tetangga. Dalam kasus terburuk, antrean membutuhkan ruang O(rows × cols).

Mengapa menggunakan BFS, bukan DFS, untuk masalah Jeruk Membusuk?

Pencarian breadth first mengunjungi sel berdasarkan jaraknya dari sumber, dan jarak di sini berarti waktu: level k adalah kumpulan jeruk yang membusuk pada menit ke-k. Pencarian depth first bisa mencapai sebuah sel melalui jalan memutar yang panjang terlebih dahulu, lalu harus mengunjunginya kembali setiap kali menemukan rute yang lebih pendek.

Bisakah kamu menyelesaikan masalah Jeruk Membusuk tanpa mengubah grid?

Ya. Gunakan array visited terpisah dan periksa array tersebut alih-alih menulis 2 ke dalam grid. Ini memerlukan memori tambahan sebesar O(rows × cols), yang mungkin tetap dibutuhkan oleh queue, dan grid milik pemanggil tetap seperti semula.

def orangesRotting(grid):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

Output yang diharapkan