Bağlı bölgeyi yeniden boya
Görev tanımı
Problem
Sayılardan oluşan bir grid bir görüntünün renklerini temsil ediyor. Bir başlangıç hücresi ve yeni bir renk verildiğinde, başlangıç hücresini ve ondan yukarı, aşağı, sola ya da sağa adımlarla, yalnız başlangıç hücresinin orijinal rengindeki hücrelerden geçerek ulaşılabilen her hücreyi yeniden boya. Grid'i döndür.
Örnekler
Input: grid = [[1, 1, 1],
[1, 1, 0],
[1, 0, 1]], row = 1, col = 1, colour = 2
Output: [[2, 2, 2],
[2, 2, 0],
[2, 0, 1]]
Neden: sağ alttaki 1 bölgeye yalnız çapraz değiyor, bu yüzden kalıyor
Input: grid = [[5]], row = 0, col = 0, colour = 3
Output: [[3]]
Input: grid = [[0, 0],
[0, 0]], row = 0, col = 0, colour = 0
Output: [[0, 0],
[0, 0]]
Neden: edge case: aynı renkle yeniden boyamak hiçbir şeyi değiştirmez
İpuçları
0 / 3
Bölge bağlantıyla tanımlanıyor; yani iş bütün grid'in bir taraması değil, başlangıç hücresinden dışa doğru bir dolaşma.
Bir hücreyi iki kez ziyaret etmekten kaçınmanın bir yoluna ihtiyacın var. Yeni renk eskisinden farklı olduğu sürece bir hücreyi yeni renge boyamak onu zaten işaretler.
Orijinal rengi hatırla ve yeni renge eşitse hemen dön. Değilse başlangıcı bir stack'e push et. Bir hücreyi pop et; grid'in içindeyse ve hâlâ orijinal rengi taşıyorsa onu boya ve dört komşusunu push et. Stack boşalınca dur.
- Hedef zaman
- O(rows · cols)
- Hedef alan
- O(rows · cols)
Çözüm
Bu, başlangıçtan dışa doğru düz bir derinlik öncelikli yayılma; boyanın kendisi ziyaret işareti görevi görür: bir hücre yeni rengi tuttuğu anda artık orijinalle eşleşmez ve bir daha genişletilmez. Bu yöntem yalnız iki renk farklıyken işe yarar; eşit renklerin erken dönmesinin sebebi bu. O kontrol olmadan aynı hücreler sonsuza kadar push edilirdi. Açık bir stack derin bölgelerin call stack'i tüketmesini engeller. Bölgedeki her hücre bir kez boyanır ve dört komşu push eder; zaman O(rows * cols), stack en kötü durumda O(rows * cols).
def repaint(grid, row, col, colour):
old = grid[row][col]
if old == colour:
return grid # nothing to do, and no endless loop
stack = [(row, col)]
while stack:
r, c = stack.pop()
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == old:
grid[r][c] = colour # painting doubles as the visited mark
stack += [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
return grid
print(repaint([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)) # -> [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(repaint([[5]], 0, 0, 3)) # -> [[3]]
print(repaint([[0, 0], [0, 0]], 0, 0, 0)) # -> [[0, 0], [0, 0]]Kodda değil de fikirde mi takıldın? Flood fill bunu anlatıyor.