Swim in Rising Water
Sana, 0'dan n²-1'e kadar olan her sayıyı tam olarak bir kez içeren, yüksekliği n × n olan bir ızgara veriliyor. t anında suyun yüksekliği her yerde t'dir; 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. Her ikisi de su altındayken, bir kenarı senin hücrenle ortak olan bir hücreye hiç zaman kaybetmeden yüzebilirsin. Sağ alt hücrede bulunabileceğin en erken zamanı döndür.
Fonksiyon
- 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].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- 0'dan
n²-1'e kadar her değer tam olarak bir kez görünür.
Örnekler
- Girdi
- grid = [[0, 2], [3, 1]]
- Çıktı
- 2
- Açıklama
- Üst sağ hücreden geçen güzergâh 0, 2, 1 şeklindedir; en yüksek hücresi 2'dir. Alt sol hücreden geçen güzergâh 0, 3, 1 şeklindedir; en yüksek hücresi 3'tür. 2. zamanda ilk güzergâh su altındadır.
- Girdi
- 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]]
- Çıktı
- 16
- Açıklama
- 15 zamanında yalnızca üst sıraya ve onun sonunun altındaki 5'e ulaşırsın; dışarı çıkan her yol 16 veya daha fazlasından geçer. 16'dan başlayıp 15, 14, 13, 12, 11 ve alt sıra üzerinden dolaşmak hiçbir zaman 16'nın üzerine çıkmaz.
- Girdi
- grid = [[3, 0], [1, 2]]
- Çıktı
- 3
- Açıklama
- Başlangıç hücresinin yüksekliği 3'tür, bu nedenle 3. zamandan önce orada bulunamaz ve oradan ayrılamazsınız. O zamana kadar tüm ızgara su altında kalır.
Ek soru
Eğer yükseklikler tekrar edebilse ve 10^9'a ulaşabilseydi, yaklaşımlarınızdan hangisi değişmeden çalışmaya devam ederdi ve ne üzerinde ikili arama yapardınız?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Su seviyesinin
tolduğunu bildiğinizi varsayalım. Geçiş yolu olup olmadığını söyleyebilir misiniz?tarttıkça bu yanıt nasıl değişir?Bir rotanın üzerindeki her hücrenin suyla kaplanması gerekir; bu nedenle rotanın ihtiyaç duyduğu süre, üzerindeki en yüksek hücrenin yüksekliğidir. En yüksek hücresi mümkün olduğunca alçak olan köşeler arasındaki rotayı istiyorsun.
Test olarak flood fill kullanarak
tüzerinde ikili arama yapın veya bir hücrenin zamanının, hücreye ulaştığınız zaman ile hücrenin kendi yüksekliğinden büyük olanı olduğu bir min-heap ile Dijkstra algoritmasını çalıştırın. Sağ alt hücre heap'ten çıkınca durun.
Çözüm
Bir rota, en yüksek hücresi kadar zaman gerektirir; çünkü su, geçtiğin her hücreyi kaplamalıdır. Bu yüzden köşeler arasındaki en yüksek hücresi en düşük olan rotayı bul: maliyeti toplam değil, maksimum olan en kısa yol. Suyu adım adım yükselt, seviyeyi ikili aramayla bul veya bu maliyet üzerinde Dijkstra algoritmasını çalıştır.
Suyu her seferinde bir adım yükselt
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Su seviyesini t olarak sabitle. Sol üstten başlayıp yüksekliği en fazla t olan hücrelerden ilerleyen bir su baskını doldurması, sağ alt köşeye ulaşılıp ulaşılamadığını söyler. Her iki köşenin de su altında kalması gerektiğinden, t değerini yüksek olan köşenin yüksekliğinden, max(grid[0][0], grid[n-1][n-1]), başlat ve doldurma ilerleyene kadar 1 artır. Su yükseldikçe yalnızca yeni hücreler açılır; bu yüzden işe yarayan ilk seviye cevaptır.
Her doldurma O(n²) maliyetindedir ve su neredeyse n² kez yükselebilir: 100 × 100'lük bir ızgarada, 10^4 seviyeye × 10^4 hücreye kadar, yani yaklaşık 10^8 hücre ziyareti.
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 bir ziyaret edildi işareti kullanarak, yüksekliği en fazla
tolan hücrelerden sol üstten başlayarak taşma doldurma yap. - Doldurma sağ alta ulaşırsa
t'yi döndür. - Aksi takdirde
t'ye 1 ekle ve doldurma işlemini yeniden yap.
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 tSu seviyesi üzerinde ikili arama
Sezgi
Taşkın doldurma testi, cevabın altındaki her seviye için başarısız olur ve cevaptan başlayarak tüm seviyeler için başarılı olur. İkili arama, yüksek köşe ile n²-1 arasında, tüm ızgaranın su altında kaldığı eşiği bulur.
5 × 5 örneğinde lo = 6 ve hi = 24. 15. seviye başarısız olur, bu yüzden lo = 16. 20, 18, 17 ve 16. seviyelerin tümü başarılı olur ve arama beş doldurma işleminden sonra 16'da sona erer.
100 × 100 boyutunda bir ızgarada 10^4 seviye vardır; dolayısıyla karara varmak için yaklaşık 14 doldurma işlemi yeterlidir: 10^8 yerine yaklaşık 1.4 × 10^5 hücre ziyareti.
Algoritma
lodeğerini daha yüksek köşe yüksekliğine,hideğerini isen²-1değerine ayarla.lo < hiolduğu sürece, aşağı yuvarlanmışmid = (lo + hi) / 2değerini al.midseviyesinde taşma doldurma yap. Sağ alt köşeye ulaşırsahi = midolarak ayarla; aksi takdirdelo = mid + 1olarak ayarla.lodeğerini 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 loRotanın en yüksek hücresinde Dijkstra
Sezgi
Her rotaya bir maliyet verin: rotadaki en yüksek hücrenin yüksekliği. Dijkstra algoritması yine çalışır, çünkü yüksekliği h olan bir hücreye giden rotayı uzatmanın maliyeti max(old cost, h) olur; bu maliyet hiçbir zaman eski maliyetten düşük değildir. Bu süreye göre sıralanmış hücreleri tutan bir min yığını kullanın ve sol üst köşedeki hücreyi grid[0][0] ile başlatın. Sağ alt köşe yığından çıktığında, o hücrenin süresi cevaptır.
Bir hücreyi yığına ilk eklediğinizde görülmüş olarak işaretleyebilirsiniz. Hücreler yığından süre sırasına göre çıkar; bu nedenle bir komşuya ulaşan ilk hücre, o komşuya verilebilecek en küçük süreyi sağlar ve her hücre yığına yalnızca bir kez girer.
Yığın, ulaşabileceğiniz alanın sınırını tutar ve her çıkarma, oraya adım atmaya yetecek kadar su seviyesini yükseltir. 5 × 5 örneğinde çıkarılan hücrelerin süreleri 0, 1, 2, 3, 4, 5, ardından kapıdaki 16'dır; sağ alt köşe ise 16 ile çıkar.
Algoritma
- Sol üst hücreyi ziyaret edilmiş olarak işaretle ve
grid[0][0]zamanı ile kuyruğa ekle. - En küçük
tzamanına sahip hücreyi kuyruktan çıkar. Sağ alt hücreysetdeğerini döndür. - Henüz ziyaret edilmemiş her komşuyu ziyaret edilmiş olarak işaretle ve
max(t, its height)zamanı ile kuyruğa ekle. - 2. adımdan itibaren tekrarla.
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
- Bir köşenin kendi yüksekliğini göz ardı etmek. Yanıt en az
grid[0][0]vegrid[n-1][n-1]değerleri kadar olmalıdır:[[3, 0], [1, 2]]için yanıt 3'tür. - En düşük komşuya açgözlü bir şekilde ilerlemek. En iyi rota, 5 × 5 örneğinde olduğu gibi, bir kapıya tırmanıp ardından uzun yoldan geçmeyi gerektirebilir.
- Rota boyunca yükseklikleri toplamak, tıpkı sıradan bir en kısa yol probleminde olduğu gibi. Yeni süre
t + heightdeğil,max(t, height)olur. - Taşkın doldurma işlemi 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.
Sıkça sorulan sorular3
Yükselen Suda Yüzme işleminin zaman karmaşıklığı nedir?
Dijkstra algoritmasıyla O(n² log n): n² hücrenin her biri bir yığında en fazla bir kez eklenip çı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. Her ikisi de O(n²) bellek kullanır.
Can Swim in Rising Water ikili aramayla çözülebilir mi?
Evet. t seviyesinde karşıya geçip geçemeyeceğin, cevapta bir kez, false değerinden true değerine döner. Test olarak flood fill kullanarak t üzerinde ikili arama yapmak yaklaşık log2(n²) dolgu gerektirir; 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 iki köşe aynı kümeye girer girmez durun. En son açtığınız hücrenin yüksekliği cevaptır. 0 ile n²-1 arasındaki her değer bir kez geçtiğinden, yükseklikten hücreye eşleme yapan bir tablo sıralama yapmadan sırayı verir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def swimInWater(grid):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
grid = [[0, 2], [3, 1]]
Beklenen Çıktı
2