Swim in Rising Water
Kamu mendapatkan grid n × n yang berisi ketinggian dan memuat setiap angka dari 0 hingga n²-1 tepat satu kali. Pada waktu t, air berada pada ketinggian t di semua tempat, sehingga setiap sel dengan ketinggian t atau kurang berada di bawah air. Kamu mulai di sel kiri atas. Kamu bisa berenang tanpa menghabiskan waktu ke sel yang berbagi sisi dengan selmu saat keduanya berada di bawah air. Kembalikan waktu paling awal saat kamu bisa berada di sel kanan bawah.
Fungsi
- gridinteger-2d-array
- tinggi-tinggi, sebagai list yang terdiri dari n baris dengan masing-masing n angka
- Mengembalikaninteger
- waktu paling awal kamu dapat mencapai sel kanan bawah
Batasan
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Setiap nilai dari 0 hingga
n²-1muncul tepat satu kali.
Contoh
- Input
- grid = [[0, 2], [3, 1]]
- Output
- 2
- Penjelasan
- Melalui sel kanan atas, rutenya adalah 0, 2, 1, dengan sel tertinggi 2. Melalui sel kiri bawah, rutenya adalah 0, 3, 1, dengan sel tertinggi 3. Pada waktu 2, rute pertama berada di bawah air.
- Input
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- Output
- 16
- Penjelasan
- Pada waktu 15, kamu hanya mencapai baris teratas dan angka 5 di bawah ujungnya. Setiap jalan keluar melewati 16 atau lebih. Berputar dari 16 melalui 15, 14, 13, 12, 11, lalu baris terbawah tidak pernah naik di atas 16.
- Input
- grid = [[3, 0], [1, 2]]
- Output
- 3
- Penjelasan
- Sel awal memiliki ketinggian 3, jadi kamu tidak bisa berada di sana dan tidak bisa meninggalkannya sebelum waktu 3. Saat itu, seluruh grid sudah terendam air.
Pertanyaan lanjutan
Jika tinggi bisa berulang dan mencapai 10^9, pendekatan mana yang tetap berfungsi tanpa perubahan, dan apa yang akan kamu jadikan dasar pencarian biner?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Misalkan kamu mengetahui ketinggian air
t. Bisakah kamu mengetahui apakah ada jalan untuk melewatinya? Bagaimana jawaban itu berubah saattbertambah?Sebuah rute membutuhkan air untuk menutupi setiap sel yang dilaluinya, jadi waktu yang dibutuhkan rute adalah ketinggian sel tertingginya. Kamu ingin rute antara sudut-sudut dengan sel tertinggi serendah mungkin.
Gunakan pencarian biner pada
tdengan flood fill sebagai pengujian, atau jalankan algoritma Dijkstra dengan min-heap, dengan waktu untuk sebuah sel adalah nilai yang lebih besar antara waktu saat kamu tiba dan ketinggian sel itu sendiri. Berhenti saat sel kanan bawah keluar dari heap.
Solusi
Sebuah rute membutuhkan waktu sebanyak waktu yang dibutuhkan oleh sel tertingginya, karena air harus menutupi setiap sel yang kamu lewati. Jadi, cari rute antara kedua sudut yang sel tertingginya paling rendah: jalur terpendek yang biayanya adalah nilai maksimum, bukan jumlahnya. Naikkan permukaan air langkah demi langkah, gunakan pencarian biner untuk menentukan ketinggiannya, atau jalankan algoritma Dijkstra dengan biaya tersebut.
Naikkan ketinggian air satu tingkat setiap kali
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Tetapkan ketinggian air t. Satu pengisian area dari kiri atas, melalui sel dengan ketinggian paling tinggi t, memberi tahu apakah kanan bawah dapat dicapai. Mulai t dari sudut yang lebih tinggi, max(grid[0][0], grid[n-1][n-1]), karena kedua sudut harus berada di bawah air, lalu tambahkan 1 sampai pengisian area berhasil mencapai tujuan. Kenaikan air hanya membuka sel, jadi ketinggian pertama yang berhasil adalah jawabannya.
Setiap pengisian area membutuhkan O(n²), dan air dapat naik hampir n² kali: pada grid 100 × 100, hingga 10^4 tingkat × 10^4 sel, sekitar 10^8 kunjungan sel.
Algoritma
- Atur
tke nilai yang lebih tinggi dari kedua tinggi sudut. - Lakukan flood fill dari kiri atas melalui sel dengan tinggi paling banyak
t, menggunakan stack eksplisit dan tanda sudah dikunjungi pada setiap sel. - Jika pengisian mencapai kanan bawah, kembalikan
t. - Jika tidak, tambahkan 1 ke
tlalu lakukan pengisian lagi.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# You cannot finish before the water covers both corners.
t = max(grid[0][0], grid[n - 1][n - 1])
# Raise the water one step at a time until a way through opens.
while not canReach(grid, t):
t += 1
return tPencarian biner pada tingkat air
Intuisi
Uji flood fill gagal untuk setiap level di bawah jawabannya dan berhasil untuk setiap level mulai dari jawabannya. Pencarian biner menemukan titik perubahan itu, di antara sudut yang lebih tinggi dan n²-1, saat seluruh grid berada di bawah air.
Dalam contoh 5 × 5, lo = 6 dan hi = 24. Level 15 gagal, jadi lo = 16. Level 20, 18, 17, dan 16 semuanya berhasil, dan pencarian berakhir di 16 setelah lima pengisian.
Grid 100 × 100 memiliki 10^4 level, jadi sekitar 14 pengisian sudah cukup untuk menentukannya: sekitar 1.4 × 10^5 kunjungan sel, bukan 10^8.
Algoritma
- Tetapkan
loke ketinggian sudut yang lebih tinggi danhiken²-1. - Selama
lo < hi, ambilmid = (lo + hi) / 2, dibulatkan ke bawah. - Lakukan pengisian area pada tingkat
mid. Jika mencapai sudut kanan bawah, tetapkanhi = mid; jika tidak, tetapkanlo = mid + 1. - Kembalikan
lo.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# The answer lies between the higher corner and the highest cell.
lo = max(grid[0][0], grid[n - 1][n - 1])
hi = n * n - 1
# canReach is false below the answer and true from it on: find the first true.
while lo < hi:
mid = (lo + hi) // 2
if canReach(grid, mid):
hi = mid
else:
lo = mid + 1
return loDijkstra pada sel tertinggi di rute
Intuisi
Beri setiap jalur biaya sebesar nilai sel tertingginya. Algoritma Dijkstra tetap berfungsi, karena memperpanjang jalur ke sel dengan tinggi h membutuhkan biaya max(old cost, h), yang tidak pernah lebih kecil daripada biaya sebelumnya. Simpan sel dalam min-heap yang diurutkan berdasarkan waktu, dimulai dari sel kiri atas pada grid[0][0]. Saat sel kanan bawah dikeluarkan dari heap, waktunya adalah jawabannya.
Kamu bisa menandai sel sebagai sudah dikunjungi saat pertama kali memasukkannya. Sel dikeluarkan dari heap berdasarkan urutan waktu, jadi sel pertama yang mencapai tetangga akan memberinya waktu terkecil yang mungkin, dan setiap sel masuk ke heap satu kali.
Heap menyimpan tepi area yang bisa kamu jangkau, dan setiap pengeluaran menaikkan permukaan air tepat secukupnya agar kamu bisa melangkah ke sana. Dalam contoh 5 × 5, sel dikeluarkan dengan waktu 0, 1, 2, 3, 4, 5, lalu gerbang pada 16, dan sel kanan bawah dikeluarkan dengan waktu 16.
Algoritma
- Tandai bagian kiri atas sebagai sudah dikunjungi dan masukkan dengan waktu
grid[0][0]. - Ambil sel dengan waktu terkecil
t. Jika itu bagian kanan bawah, kembalikant. - Untuk setiap tetangga yang belum dikunjungi, tandai dan masukkan dengan waktu
max(t, its height). - Ulangi dari langkah 2.
import heapq
def swimInWater(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
# (time, row, col): the time is the highest cell on the best path found to that cell.
heap = [(grid[0][0], 0, 0)]
while True:
t, r, c = heapq.heappop(heap)
# Cells leave the heap in order of time, so this is the earliest you can be here.
if r == n - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
# Reached for the first time from the cell with the smallest time:
# no later route can arrive earlier, so mark it now.
seen[nr][nc] = True
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
Jebakan dan kasus tepi
- Mengabaikan ketinggian sudut itu sendiri. Jawabannya setidaknya
grid[0][0]dangrid[n-1][n-1]: untuk[[3, 0], [1, 2]], jawabannya adalah 3. - Berjalan dengan rakus menuju tetangga yang paling rendah. Rute terbaik mungkin harus mendaki ke gerbang, lalu mengambil jalan memutar yang jauh, seperti pada contoh 5 × 5.
- Menjumlahkan ketinggian sepanjang rute, seperti pada pencarian jalur terpendek biasa. Waktu yang baru adalah
max(t, height), bukant + height. - Menggunakan rekursi untuk flood fill. Rute berliku bisa terdiri dari ribuan sel, sehingga batas Python sebanyak 1.000 pemanggilan bersarang terlampaui.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu Swim in Rising Water?
O(n² log n) dengan algoritma Dijkstra: setiap dari n² sel dimasukkan ke heap dan dikeluarkan darinya paling banyak satu kali. Pencarian biner pada ketinggian air memiliki batas yang sama, sekitar log2(n²) pengisian area sebesar O(n²). Keduanya menggunakan memori O(n²).
Bisakah Can Swim in Rising Water diselesaikan dengan pencarian biner?
Ya. Kemampuanmu untuk menyeberang pada tingkat t berubah sekali, dari false menjadi true, pada jawabannya. Pencarian biner atas t dengan flood fill sebagai pengujian membutuhkan sekitar log2(n²) kali flood fill, yaitu 14 kali untuk grid 100 × 100.
Bisakah union-find menyelesaikan Swim in Rising Water?
Ya. Buka sel berdasarkan urutan ketinggiannya, gabungkan setiap sel baru dengan tetangga yang terbuka, lalu berhenti segera setelah kedua sudut berada dalam set yang sama. Ketinggian sel yang terakhir kamu buka adalah jawabannya. Karena setiap nilai dari 0 hingga n²-1 muncul satu kali, tabel dari ketinggian ke sel menunjukkan urutannya tanpa perlu mengurutkan.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def swimInWater(grid):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
grid = [[0, 2], [3, 1]]
Output yang diharapkan
2