Swim in Rising Water

Q: Yükselen Suda Yüzme algoritmasının zaman karmaşıklığı nedir?

Dijkstra algoritmasıyla O(n² log n): n² hücrenin her biri, en fazla n² giriş içeren bir yığında en fazla bir kez eklenir ve çıkarılır. Su seviyesi üzerinde ikili arama da aynı sınıra sahiptir; her biri O(n²) olan yaklaşık log2(n²) taşma doldurma işlemi yapılır. Her ikisi de ziyaret işaretleri ve yığın ya da yığın için O(n²) bellek kullanır.

Q: Maliyet en yüksek hücre olduğunda Dijkstra algoritması neden çalışır?

Dijkstra için tek bir özellik gerekir: bir rotayı uzatmak maliyetini hiçbir zaman düşürmez. Burada yeni maliyet max(t, height) olur; bu değer hiçbir zaman t 'den küçük değildir, dolayısıyla özellik sağlanır. Bu nedenle bir hücre yığından ilk kez çıktığında zamanı kesinleşmiştir ve hedefte durabilirsin.

Q: Yükselen Suda Yüzme problemi ikili aramayla çözülebilir mi?

Evet. t seviyesinde karşıya geçip geçemeyeceğin, cevabın altındaki her seviye için false, cevaptan itibaren ise true değerini alır. Test olarak bir taşkın doldurma kullanarak t üzerinde ikili arama yapmak, cevabı yaklaşık log2(n²) testte bulur: 100 × 100'lük bir ızgara için 14.

Q: Birleşim-bulma, Yükselen Suda Yüzme problemini çözebilir mi?

Evet. Hücreleri yükseklik sırasına göre açın, her yeni hücreyi açık komşularıyla birleştirin ve sol üst ile sağ alt hücre aynı kümede olur olmaz durun. En son açtığınız hücrenin yüksekliği yanıttır. Izgarada 0 ile n²-1 arasındaki her değer bir kez bulunduğundan, yükseklikten hücreye eşleme yapan bir tablo sıralama yapmadan açılma sırasını verir.

ZorEn kısa yollar Yığın (heap)İkili arama

+10

Her sayıyı tam olarak bir kez içeren, satır listesi olarak verilmiş yüksekliklerden oluşan n × n boyutunda bir ızgaranız var; sayılar 0 ile n²-1 arasındadır. Yağmur 0 anında başlar ve t anında su her yerde t yüksekliğindedir; dolayısıyla yüksekliği t veya daha az olan her hücre su altındadır. Sol üst hücrede başlarsınız. İkisi de su altındayken bir hücreden kenar paylaştığı bir hücreye yüzebilirsiniz ve yüzmek zaman almaz. Sağ alt hücrede bulunabileceğiniz en erken zamanı döndürün.

Fonksiyon

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

gridinteger-2d-array: yükseklikler, her biri n sayıdan oluşan n satırlık bir liste olarak
Döndürürinteger: sağ alt hücreye ulaşabileceğin en erken zaman

Kısıtlar

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
0 ile n²-1 arasındaki her değer tam olarak bir kez görünür.

Örnekler

Girdi: grid = [[0, 2], [3, 1]]
Çıktı: 2
Açıklama: Sağ üst hücreden geçen rota 0, 2, 1 şeklindedir ve en yüksek hücresi 2'dir. Sol alt hücreden geçen rota 0, 3, 1 şeklindedir ve en yüksek hücresi 3'tür. 2. zamanda ilk rota su altında kalır, bu yüzden cevap 2'dir.

Gönderirken +13 gizli test

Ek soru

Yükseklikler tekrarlanabilse ve 10^9'a ulaşabilse, yaklaşımlarından hangisi hiçbir değişiklik yapmadan çalışmaya devam ederdi ve ne üzerinde ikili arama yapardın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir rotanın ihtiyaç duyduğu su seviyesi, geçtiğiniz her hücreyi suyun kaplaması gerektiğinden, rotadaki en yüksek hücrenin seviyesidir. Bu nedenle amaç, en yüksek hücresi mümkün olduğunca düşük olan köşeler arasındaki rotayı bulmaktır: Bir yolun maliyetinin toplamı değil, en yüksek değeri olduğu en kısa yol. Suyu her seferinde bir seviye yükseltip test edebilir, aynı testi kullanarak su seviyesinde ikili arama yapabilir veya maliyet olarak en yüksek hücreyi kullanan Dijkstra algoritmasını çalıştırabilirsiniz.

Su seviyesini her seferinde bir adım yükseltin

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir su seviyesi t belirleyin. Ulaşabileceğiniz hücreler, yüksekliği en fazla t olan ve bu tür hücreler üzerinden başlangıca bağlanan hücrelerdir. Sol üstten başlayarak yapılan bir taşma doldurma işlemi bunları bulur: başlangıç hücresini ekleyin, bir hücreyi çıkarın, yüksekliği en fazla t olan ziyaret edilmemiş her komşuyu ekleyin. Sağ alt köşeye ulaşılırsa, t zamanı yeterlidir.

Yanıt, taşma doldurma işleminin hedefine ulaştığı en küçük t değeridir. Her iki köşe de suyun altında kalması gerektiğinden, bu değer yüksek olan köşeden, yani max(grid[0][0], grid[n-1][n-1]) değerinden küçük olamaz. Bu değerden başlayın ve doldurma işlemi başarılı olana kadar 1 ekleyin. İşe yarayan ilk seviye yanıttır; çünkü su yükseldikçe yalnızca yeni hücreler açılır, hiçbir hücre kapanmaz: işe yarayan bir seviye işe yaramaya devam eder.

Her test O(n²) maliyetlidir ve su hedefe ulaşmadan önce neredeyse n² kez yükselebilir. 100 × 100'lük bir ızgarada bu, 10^4 seviye × 10^4 hücre, yani yaklaşık 10^8 hücre ziyareti demektir. Büyük testlerde köşelerde 0 ve 1 bulunur ve yanıtlar 4,950 ile 9,998 arasında yer alır; dolayısıyla yanıt bulunana kadar binlerce tam taşma doldurma işlemi çalışır.

Algoritma

t'yi iki köşe yüksekliğinden büyük olana ayarla.
Açık bir yığın ve her hücre için ziyaret edildi işareti kullanarak, yüksekliği en fazla t olan hücrelerden sol üstten başlayıp taşarak doldur.
Doldurma sağ alt köşeye ulaşırsa t'yi döndür.
Aksi takdirde t'ye 1 ekle ve yeniden doldur.

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 t

Su seviyesi üzerinde ikili arama

Sezgi

İlk yaklaşımdaki testin kullanışlı bir özelliği vardır. Yanıtın altındaki her düzeyde başarısız olur, yanıt düzeyinden itibaren her düzeyde başarılı olur. Bir kez, hayırdan evete dönen bir evet ya da hayır sorusunun yanıtını ikili arama, logaritmik sayıda denemeyle bulur.

lo (yüksek köşe) ile tüm ızgaranın su altında olduğu ve testin başarılı olması gereken en yüksek hücre hi = n²-1 arasında arama yap. Orta düzeyi test et. Geçebiliyorsan yanıt en fazla mid değeridir; bu yüzden hi = mid yap. Geçemiyorsan yanıt mid değerinden büyüktür; bu yüzden lo = mid + 1 yap. İkisi eşitlendiğinde o düzey yanıttır.

5 × 5 örneğinde lo = 6 ve hi = 24. 15. düzey başarısız olur, çünkü üst bölgenin çıkışı kapanmıştır; bu nedenle lo = 16 olur. 20, 18, 17 ve 16. düzeylerin tümü başarılı olur ve hi değerini 16'ya indirir; arama beş taşma doldurma işleminden sonra 16'da sona erer.

100 × 100 boyutundaki bir ızgarada 10^4 düzey vardır; dolayısıyla yaklaşık 14 test yeterlidir ve her biri O(n²) sürer: 10^8 yerine yaklaşık 1.4 × 10^5 hücre ziyareti. Taşma doldurma işlemini yinelemeli yap. Büyük testlerden biri, Python'ın 1.000 iç içe çağrı sınırından çok daha derin, yaklaşık 5.000 hücre uzunluğunda kıvrımlı bir koridordur.

Algoritma

lo'yu daha yüksek köşe yüksekliğine, hi'ı ise n²-1'e ayarla.
lo < hi olduğu sürece, aşağı yuvarlanmış mid = (lo + hi) / 2 değerini al.
mid seviyesinde taşma doldurma işlemi yap. Sağ alt köşeye ulaşırsa hi = mid olarak ayarla; aksi hâlde lo = mid + 1 olarak ayarla.
lo'yu döndür.

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 lo

Rotanın en yüksek hücresinde Dijkstra

Sezgi

Izgarayı bir grafik olarak ele al ve her rotaya, adımlarının toplamını değil, en yüksek hücresini maliyet olarak ver. Bir rotayı uzatmak onu hiçbir zaman daha ucuz hâle getirmediğinden, bu maliyetle Dijkstra algoritması yine çalışır. Daha uzun rotanın maliyeti max(old cost, new height) olur; bu değer hiçbir zaman eski maliyetten düşük değildir ve Dijkstra'nın ihtiyaç duyduğu özellik de budur.

Hücreleri, onlara bulunan en iyi rotadaki en yüksek hücre olan sürelerine göre sıralayan bir min yığını tut. Sol üst hücreden, süre olarak grid[0][0] ile başla. Süresi en küçük olan t hücresini çıkar; görmediğin her komşuya max(t, its height) süresini ata. Sağ alt hücre yığından çıktığında, süresi cevaptır.

Bir hücreyi ilk kez yığına eklediğinde görülmüş olarak işaretleyebilirsin. Hücreler yığından süre sırasına göre çıkar; dolayısıyla bir komşuya ulaşan ilk hücrenin süresi, ona ulaşacak diğer tüm hücrelerinkinden küçüktür ve bu hücreden komşuya giden rotanın süresi mümkün olan en iyisidir. Daha sonraki bir rota en az o kadar büyük bir süreyle ulaşır. Böylece her hücre, son süresiyle yığına yalnızca bir kez girer.

Bu, suyun adım adım yükselmesidir. Yığın, ulaşabileceğin alanın sınırını tutar; en düşük hücreyi çıkarmak, oraya adım atabilecek kadar suyun yükselmesidir. 5 × 5 örneğinde çıkarılan hücrelerin süreleri 0, 1, 2, 3, 4, 5, ardından da 16 olan kapıdır. Bundan sonra dolambaçlı yoldaki her hücrenin süresi 16 olur ve sağ alt hücre, daha yüksek süreli herhangi bir hücreden önce, 16 süresiyle yığından çıkar.

n² hücrenin her biri en fazla bir kez eklenip çıkarılır ve her işlem O(log n) sürer; bu nedenle zaman karmaşıklığı O(n² log n) olur. Arama, hedef yığından çıkar çıkmaz durur.

Algoritma

Sol üst köşeyi ziyaret edilmiş olarak işaretleyin ve grid[0][0] zamanı ile yığına ekleyin.
Zamanı t olan en küçük hücreyi çıkarın. Sağ alt köşedeyse t değerini döndürün.
Henüz ziyaret edilmemiş her komşuyu ziyaret edilmiş olarak işaretleyin ve max(t, its height) zamanı ile yığına ekleyin.
2. adımdan tekrarlayın.

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))

Tuzaklar ve uç durumlar

Yanlış cevapların çoğu, unutulan bir köşeden, toplanmak yerine en büyüğü alınan bir maliyetten veya aramayı çok erken sonlandırmaktan kaynaklanır.

Başlangıç hücresinin kendi yüksekliğini göz ardı etmek. Sol üst köşede, su seviyesi bu hücrenin yüksekliğine ulaşmadan bulunamazsın; dolayısıyla cevap en az grid[0][0] olur. [[3, 0], [1, 2]] için cevap 3'tür.
Hedef hücrenin yüksekliğini göz ardı etmek. Sağ alt köşedeki hücrenin de su altında kalması gerekir; dolayısıyla cevap en az grid[n-1][n-1] olur.
Bulunduğun hücrenin en alçak komşusuna açgözlü biçimde ilerlemek. 5 × 5 örneğinde olduğu gibi, en iyi rota bir geçide tırmanıp ardından uzun bir dolambaçlı yoldan geçebilir. Bunu yalnızca ulaşılan alanın tüm sınırını tarayan bir arama bulabilir.
Sıradan bir en kısa yol probleminde olduğu gibi rota üzerindeki yükseklikleri toplamak. Yeni süre max(t, height) olur, t + height değil.
Taşkın doldurma için özyineleme kullanmak. Dolambaçlı bir rota binlerce hücre uzunluğunda olabilir ve bu da Python'ın 1.000 iç içe çağrı sınırını aşar.
Çapraz hareket etmek. Yalnızca seninkiyle bir kenarı ortak olan bir hücreye yüzebilirsin.

Sıkça sorulan sorular4

Yükselen Suda Yüzme algoritmasının zaman karmaşıklığı nedir?

Dijkstra algoritmasıyla O(n² log n): n² hücrenin her biri, en fazla n² giriş içeren bir yığında en fazla bir kez eklenir ve çıkarılır. Su seviyesi üzerinde ikili arama da aynı sınıra sahiptir; her biri O(n²) olan yaklaşık log2(n²) taşma doldurma işlemi yapılır. Her ikisi de ziyaret işaretleri ve yığın ya da yığın için O(n²) bellek kullanır.

Maliyet en yüksek hücre olduğunda Dijkstra algoritması neden çalışır?

Dijkstra için tek bir özellik gerekir: bir rotayı uzatmak maliyetini hiçbir zaman düşürmez. Burada yeni maliyet max(t, height) olur; bu değer hiçbir zaman t'den küçük değildir, dolayısıyla özellik sağlanır. Bu nedenle bir hücre yığından ilk kez çıktığında zamanı kesinleşmiştir ve hedefte durabilirsin.

Yükselen Suda Yüzme problemi ikili aramayla çözülebilir mi?

Evet. t seviyesinde karşıya geçip geçemeyeceğin, cevabın altındaki her seviye için false, cevaptan itibaren ise true değerini alır. Test olarak bir taşkın doldurma kullanarak t üzerinde ikili arama yapmak, cevabı yaklaşık log2(n²) testte bulur: 100 × 100'lük bir ızgara için 14.

Birleşim-bulma, Yükselen Suda Yüzme problemini çözebilir mi?

Evet. Hücreleri yükseklik sırasına göre açın, her yeni hücreyi açık komşularıyla birleştirin ve sol üst ile sağ alt hücre aynı kümede olur olmaz durun. En son açtığınız hücrenin yüksekliği yanıttır. Izgarada 0 ile n²-1 arasındaki her değer bir kez bulunduğundan, yükseklikten hücreye eşleme yapan bir tablo sıralama yapmadan açılma sırasını verir.

Python

def swimInWater(grid):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

Swim in Rising Water

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Su seviyesini her seferinde bir adım yükseltin

Su seviyesi üzerinde ikili arama

Rotanın en yüksek hücresinde Dijkstra

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler