Longest Increasing Path in a Matrix

ZorDinamik programlama Graflar Topolojik sıralama

+10

Satır listesi olarak, m satır ve n sütundan oluşan tam sayılardan oluşan bir ızgara olan matrix verilir. Bir yol, her seferinde bir adım yukarı, aşağı, sola veya sağa ilerleyerek hücreden hücreye gider (çapraz adımlar yoktur ve kenarlardan dönülmez) ve her adımda kesinlikle daha büyük bir değere sahip hücreye ulaşılmalıdır. Böyle bir en uzun yol üzerindeki hücre sayısını döndür. Tek bir hücre de 1 hücrelik bir yoldur.

Fonksiyon

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: eşit uzunluktaki satırlardan oluşan bir liste olarak değerler ızgarası
Döndürürinteger: en uzun kesin artan yoldaki hücre sayısı

Kısıtlar

1 ≤ m, n ≤ 100, burada m = matrix.length ve n = matrix[i].length
Her satırın uzunluğu aynıdır: n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Örnekler

Girdi: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Çıktı: 7
Açıklama: 3, 4, 5, 6, 7, 8, 9 yolu sağ sütundan aşağı, alt satır boyunca sola, orta sütundan yukarı ve köşedeki 9'a doğru sola ilerler: 7 hücre. En küçük değer daha kötü sonuç verir: 1'den başlayan en iyi yollar 1, 2, 7, 8, 9 ve 1, 6, 7, 8, 9'dur; her biri 5 hücreden oluşur.

Gönderirken +18 gizli test

Ek soru

Yalnızca uzunluğunu değil, en uzun yollardan birinin hücrelerini de döndürebilir misin?

Çözüm

Her hücreden, daha büyük bir değer taşıyan her komşuya bir ok çiz. Değerler her ok boyunca artar; bu nedenle hiçbir ok zinciri başladığı yere geri dönemez: ızgara yönlü çevrimsiz bir çizgedir ve görev, bu çizgedeki en uzun yolu bulmaktır. Genel bir çizgede bu soruyu büyük girdiler için çözmek umutsuzdur; ancak çevrimler olmadığında bir hücreden başlayan en uzun yol yalnızca o hücreye bağlıdır, bu yüzden bunu her hücre için bir kez hesaplayabilir ve tüm problemi O(m × n) düzeyine indirebilirsin. Önbelleğe alınmış derinlik öncelikli arama bunu yukarıdan aşağıya hesaplar; ızgarayı zirvelerinden başlayarak katman katman soymak, yani Kahn algoritmasını ters yönde uygulamak ise aşağıdan yukarıya hesaplar.

Artan her yolu takip edin

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

Sezgi

Her hücrede bir yürüyüş başlatın. Bulunduğunuz hücreden, değeri daha büyük olan dört komşunun her birini deneyin ve oradan daha büyük komşu kalmayana kadar aynı şekilde ilerleyin. Her yürüyüşteki hücreleri sayın ve en büyük sayıyı tutun.

Yürüyüş için ziyaret edilenler kümesi gerekmez. Değerler her adımda arttığı için yürüyüş aynı hücreye asla geri dönemez: orada yeniden durabilmek için o hücrenin değerine geri inmesi gerekirdi. Yürüyüşleri (hücre, uzunluk) girdilerinden oluşan bir yığında tutun. Bir girdiyi yığından çıkarmak o hücredeki yürüyüşü bitirir, daha büyük komşularını yığına eklemek ise yürüyüşü uzatır.

Yöntem doğrudur ama umutsuzca yavaştır, çünkü yürüyüşler dallanır. Değerlerin satır ve sütun numaralarının toplamı olduğu 100 × 100'lük bir ızgarada sağa veya aşağı atılan her adım değeri artırır ve yalnızca sol üst köşeden başlayan yürüyüşlerin sayısı bile 10^58'den fazladır. Daha da kötüsü, belirli bir hücreden başlayan yürüyüş, başka bir yürüyüş o hücreden her geçtiğinde yeniden yapılır; sonraki yaklaşımın ortadan kaldırdığı israf da budur.

Algoritma

Her hücre için yığına (hücre, 1) ekle.
Bir (hücre, uzunluk) girdisi çıkar ve yanıtı uzunluk ile güncelle.
Izgara içindeki değeri kesinlikle daha büyük olan her komşu için (komşu, uzunluk + 1) ekle.
Yığın boşalana kadar tekrarla, ardından sonraki başlangıç hücresine geç.
Görülen en büyük uzunluğu döndür.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

Kendi yığınınızla önbelleğe alınmış derinlik öncelikli arama

Sezgi

best[cell], o hücrede başlayan en uzun artan yoldaki hücre sayısı olsun. Yol ya tam orada biter ya da bir sonraki adımda daha büyük bir komşuya gidip o komşudan başlayan en uzun yol boyunca devam eder. Dolayısıyla best[cell] = 1 + max(best[nb]); burada daha büyük komşular nb üzerinden alınır, böyle komşu yoksa değer 1 olur. Döngüsüz yapı sayesinde bunu güvenle yeniden kullanabiliriz: herhangi bir yolda cell hücresinden önce gelen hücrelerin hepsi daha küçüktür, dolayısıyla bu hücreler ondan sonra gelemez ve cell hücresinden sonraki en iyi devam, oraya nasıl geldiğine bağlı olarak değişmez. Her best değerini bir kez hesaplayıp saklayın; böylece üstel sayıdaki yürüyüş ağacı, hücre başına tek ziyarete dönüşür.

İlk örnekte 9'un daha büyük komşusu yoktur, bu nedenle oradaki best değeri 1'dir. Sonra 8'in değeri 2, 7'nin 3, 6 ve 2'nin 4, 5 ve 1'in 5, 4'ün 6 ve 3'ün 7 olur; cevap budur. Her hücre 4 komşusuna bakar, dolayısıyla çalışma O(m × n) olur.

Doğal kod özyinelemelidir: bir hücre için best değerini döndüren ve her büyük komşu için kendisini çağıran bir işlev. Çağrı derinliği, izlediği yolun uzunluğuna eşittir ve kısıtlamalar her hücreden geçen bir yola izin verir: 100 × 100'lük bir ızgarada ileri geri kıvrılan değerler, 10.000 hücrelik tek bir yol oluşturabilir; ancak Python varsayılan olarak 1.000 iç içe çağrıda durur. Aşağıdaki kod özyinelemeyi kendi başına yürütür, bu nedenle hiçbir yol onun için fazla uzun değildir. Bir hücre yığını ve her hücre için dört yönden kaçını denediğinizi tutun. En üstteki hücreye bakın: denenmemiş bir yönü varsa onu deneyin ve komşu daha büyükse ve henüz tamamlanmamışsa o komşuyu yığına ekleyin. Dördü de denendiğinde, tüm büyük komşular tamamlanmış olur; bu nedenle hücreyi yığından çıkarın ve best değerini belirleyin. Bu, özyinelemeli bir çağrının izleyeceği sıranın aynısıdır.

Döngü tespitinin aksine, arama için "işlem sürüyor" işaretlemesine gerek yoktur. Yığındaki her hücre, altındaki hücreden daha büyüktür; bu nedenle en üstteki hücrenin daha büyük bir komşusu yığının daha altlarında bulunamaz.

Algoritma

best değerini 0 (henüz bilinmiyor) olarak ayarlayın ve her hücre için yön sayacını 0 yapın.
best değeri 0 olan her hücreyi bir yığına ekleyin.
En üstteki hücreye bakın. Denenecek bir yönü varsa sayacını artırın ve o yöndeki komşu ızgara içindeyse, daha büyükse ve tamamlanmamışsa onu yığına ekleyin.
Dört yönün tamamı denendiyse hücreyi yığından çıkarın ve best değerini, daha büyük komşuları arasındaki en büyük best değerinin 1 fazlası olarak ayarlayın; böyle bir komşusu yoksa 1 yapın.
En büyük best değerini döndürün.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

Izgarayı tepe noktalarından soyun

Sezgi

Dinamik programlamayı tersine çevirip, Kahn algoritmasının topolojik sıralamayı oluşturduğu gibi en üstteki değerlerden başlayarak aşağı doğru oluşturun. Hiçbir komşusu daha büyük değilse bir hücreye tepe deyin. Bir tepe noktasından başlayan yol ilerleyemez, bu yüzden 1 hücreden oluşur. Tüm tepeleri aynı anda kaldırın: bu, 1. katmandır. Şimdi bazı hücrelerin son büyük komşusu da ortadan kalkmıştır; geriye kalanların tepeleri olmuşlardır. Bunları 2. katman olarak kaldırın ve ızgara boşalana kadar devam edin. Katman sayısı cevaptır.

Nedeni: Bir hücre, kendisinden başlayan en uzun yol k hücre içeriyorsa tam olarak k. katmana düşer. Bir hücre, son büyük komşusu kaldırıldıktan sonraki turda kaldırılır; bu nedenle katmanı, büyük komşuları arasındaki en yüksek katmandan 1 fazladır. Bu da önceki yaklaşımda kullanılan best[cell] = 1 + max(best[nb]) formülüdür. En derin katman, en uzun yolun başlangıcına aittir.

İlk örnekte tek tepe 9'dur (komşuları 8 ve 2'dir). Onu kaldırmak 8'i serbest bırakır; 8'i kaldırmak 7'yi serbest bırakır; 7'yi kaldırmak 2'yi ve 6'yı serbest bırakır; bu ikisi 1'i ve 5'i serbest bırakır; 5, 4'ü; 4 ise 3'ü serbest bırakır. Böylece 7 katman oluşur ve 3, 4, 5, 6, 7, 8, 9 yolu, her katmandan bir hücreden geçerek yükselir.

Sonraki katmanı hızlıca bulmak için her hücrenin hâlâ kaç büyük komşusu olduğunu sayın. Bir hücre kaldırıldığında, ondan kesinlikle küçük olan her komşunun sayısı azalır; sayı 0'a ulaştığında bu komşu bir sonraki katmana girer. Her hücre bir kez kaldırılır ve her komşu çifti sabit sayıda incelenir; bu nedenle iş miktarı O(m × n) olur ve yığın ya da özyineleme gerekmez.

Algoritma

Her hücre için, daha büyük değere sahip komşuların sayısını hesapla.
Sayısı 0 olan her hücreyi mevcut katmana ekle.
Katman boş değilken katman sayısını 1 artır. Katmandaki her hücre için, kesin olarak daha küçük olan her komşunun sayısını azalt ve sayısı 0'a ulaşan komşuları sonraki katmana ekle.
Sonraki katmanı mevcut katman yap ve tekrarla.
Katman sayısını döndür.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

Tuzaklar ve uç durumlar

Buradaki hatalar "strictly" sözcüğünden, derin özyinelemeden ve diğer ızgara problemlerinden taşınan alışkanlıklardan kaynaklanıyor.

> yerine >= ile karşılaştırmak. Yan yana iki 4 olduğunda her biri diğerinden bir adım daha yüksek sayılır, oklar bir döngü oluşturur, kaba kuvvet yaklaşımı sürekli ileri geri gider ve önbelleğe alınmış bir arama, hâlâ hesaplanmakta olan bir uzunluğu okur.
Çok uzun yollarda özyineleme kullanmak. Özyinelemeli bir arama, yolun uzunluğu kadar çağrı derinliğine iner ve kısıtlamalar her hücreden geçen bir yola izin verir: 100 × 100'lük bir ızgarada ileri geri kıvrılan değerler, 10.000 hücrelik tek bir yol oluşturur; bu, Python'ın varsayılan 1.000 iç içe çağrı sınırının on katıdır. Bu kadar uzun yollar için kendi yığınınızı kullanan yinelemeli bir arama veya artırılmış bir özyineleme sınırı gerekir (Python'da sys.setrecursionlimit); yine de çok yüksek bir sınır, yorumlayıcının kendi yığınını taşırabilir.
Bir su baskını doldurma algoritmasında olduğu gibi, daha önce ziyaret edilen hücreleri atlamak. Tamamlanmış bir hücreye ulaşmak çıkmaz sokak değildir: o hücrede saklanan uzunluk, mevcut hücrenin tam olarak ihtiyaç duyduğu şeydir. Bu değeri okuyun, atlamayın.
Yalnızca en küçük değerden başlamak. İlk örnekte 1, 5 hücrelik bir yol verir; ancak cevap olan 7, 3'ten başlar. En uzun yol, daha küçük komşusu olmayan herhangi bir hücreden başlayabilir ve bu tür birçok hücre olabilir.
0 döndürmek. Her hücre, 1 hücrelik bir yoldur; dolayısıyla değerleri eşit olan bir ızgaranın veya 1 × 1'lik bir ızgaranın cevabı 1'dir. Her hücrenin uzunluğunu 0 değil, 1 olarak başlatın.
Katmanları soyma yaklaşımında eşit bir komşunun sayısını azaltmak. Daha büyük bir komşusunu yalnızca kesinlikle daha küçük bir komşu kaybetmiştir.

Sıkça sorulan sorular4

Bir Matristeki En Uzun Artan Yolun zaman karmaşıklığı nedir?

Önbelleğe alınmış derinlik öncelikli arama veya topolojik soyma ile O(m × n) zaman ve O(m × n) alan. m × n hücrenin her biri bir kez tamamlanır ve 4 komşusuna sabit sayıda kez bakar; ayrıca her yöntem hücre başına bir sayı tutar. Bunun yerine her hücreden başlayan tüm yolları denemek üstel zaman alır: Her değerin satır numarası ile sütun numarasının toplamı olduğu 100 × 100'lük bir ızgarada, sol üst köşeden 10^58'den fazla yol çıkar.

Bu problem neden ziyaret edilenler kümesine ihtiyaç duymaz?

Yalnızca yükselen bir yol bir hücreye asla geri dönemez; çünkü o hücrenin değerine geri inmesi gerekirdi. Bu nedenle, kesin artan olma kuralı yeniden ziyaretleri zaten engeller ve adımlar grafiğinde döngü yoktur. Önbelleğe alma işleminin güvenli olmasının nedeni de budur: belirli bir hücreden önceki hücreler, o hücreden sonraki yolu etkileyemez.

Bir Matristeki En Uzun Artan Yol, dinamik programlama mı yoksa bir graf problemi mi?

İkisi de. Bu, yönlü çevrimsiz bir grafikteki en uzun yoldur; topolojik sıralama üzerinde dinamik programlamadır: bir hücrenin cevabı, daha büyük komşuları arasındaki en iyi cevaba 1 eklenerek bulunur. Önbelleğe alınmış derinlik öncelikli arama, tabloyu aramanın hücreleri tamamladığı sırayla doldurur; topolojik katmanlama ise tepelerden başlayarak tabloyu katman katman doldurur. Hücreleri değere göre büyükten küçüğe sıralamak, sıralama için O(m × n × log(m × n)) maliyetiyle üçüncü bir geçerli sıralama sağlar.

Bu, en uzun artan alt diziden nasıl farklıdır?

Bir alt dizi bazı elemanları atlayabilir ve sıralarını korumalıdır; buradaki bir yol ise dört yönden herhangi birinde bitişik bir hücreye ilerlemelidir. Alt dizi problemi bir doğru üzerindeki dinamik programlamadır; bu problem ise bir grafa dönüştürülmüş bir ızgara üzerindeki dinamik programlamadır. Her ikisi de aynı olguya dayanır: kesin artan bir zincir kendi üzerine dönerek döngü oluşturamaz.

Python

def longestIncreasingPath(matrix):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Beklenen

Longest Increasing Path in a Matrix

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Artan her yolu takip edin

Kendi yığınınızla önbelleğe alınmış derinlik öncelikli arama

Izgarayı tepe noktalarından soyun

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler