Flood Fill

Q: Flood Fill algoritmasının zaman karmaşıklığı nedir?

m satır ve n sütundan oluşan bir görüntü için O(m × n). Bölgedeki her piksel yığına bir kez eklenir ve dört komşusuna bakar; bölgenin dışındaki piksellere ise yalnızca komşu olarak bakılır. Görüntünün tamamı tek bir bölge olduğunda yığın en fazla m × n piksel tutabilir.

Q: Flood Fill için BFS mi yoksa DFS mi kullanmalısınız?

İkisi de işe yarar ve her ikisi de O(m × n) zaman alır. Bölgeyi hangi sırayla ziyaret ettiğiniz fark etmez; bu yüzden bir kuyruk (önce genişlik) ve bir yığın (önce derinlik) aynı pikselleri boyar. Dilinizde yazması daha kısa olanı seçin ve büyük görüntülerde özyinelemeden kaçının.

Q: Yeni renk eski renkle aynı olduğunda Flood Fill neden sonsuz döngüye girer?

Olağan çözüm, “hâlâ eski renkte olmayı” “henüz ziyaret edilmemiş olmak” şeklinde ele alır. Yeni renk eski renkle aynı olduğunda bir pikseli boyamak onu değiştirmez; bu nedenle komşuları onu tekrar yığına ekler ve arama hiç bitmez. Önce bu durumu kontrol edip görüntüyü döndürmek sorunu çözer; değişmemiş görüntü doğru yanıttır.

Q: Flood Fill özyinelemeli olarak çözülebilir mi?

Evet, bir pikseli boyayan ve eski rengin her komşusunda kendini çağıran bir işlev doğrudur. Risk derinliktir: özyineleme, aramanın izlediği en uzun yol kadar derine gider; kıvrımlı bir bölgede bu, binlerce çağrı olabilir. Açık bir yığın, bu sınır olmadan aynı işi yapar.

KolayGraflar

+10

Bir görüntü, her sayının bir pikselin rengini belirttiği tam sayılardan oluşan bir ızgaradır. Görüntü sana satırlardan oluşan bir liste, sr satırında ve sc sütununda bulunan bir başlangıç pikseli ve yeni bir color olarak verilir. Başlangıç pikselini içeren bölgeyi yeniden boya: başlangıç pikselinin rengine sahip olup aynı renkteki pikseller üzerinden yukarı, aşağı, sola veya sağa ilerleyerek başlangıç pikselinden ulaşabileceğin her pikseli boya. Yeniden boyama işleminden sonraki görüntüyü döndür.

Fonksiyon

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: görüntüyü satırlardan oluşan bir liste olarak, piksel başına bir sayı
srinteger: başlangıç pikselinin 0'dan başlayarak sayılan satırı
scinteger: başlangıç pikselinin 0'dan başlayarak sayılan sütunu
colorinteger: bölge için yeni renk
Döndürürinteger-2d-array: bölge yeniden çizildikten sonraki görüntü

Kısıtlar

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Her satır aynı uzunluktadır.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length ve 0 ≤ sc < image[0].length

Örnekler

Girdi: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Çıktı: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Açıklama: Başlangıçta 1 rengi bulunur. Sağındaki 1, sol sütundaki ve alt sıradaki 1'ler ve sağ alt köşenin üzerindeki 1, başlangıca bağlıdır; bu yüzden yedisinin de değeri 5 olur. İki 0 farklı bir renktedir ve değişmeden kalır.

Gönderirken +18 gizli test

Ek soru

Köşelerde yalnızca birbirine değen pikseller de bağlantılı sayılsaydı çözümünüz nasıl değişirdi?

Çözüm

Bölge, grafın bağlantılı bir parçasıdır: Pikseller düğümlerdir ve başlangıç rengindeki, bir kenarı ortak olan iki piksel birbirine bağlanır. Verilen pikselden başlayan ve yalnızca bu renk üzerinden ilerleyen herhangi bir arama, bölgenin tamamını bulur. Dikkat edilmesi gereken iki durum, yeni rengin eski renkle aynı olduğu bir görüntü ve özyinelemeli aramayı bozan uzun, dolambaçlı bir bölgedir.

Özyinelemeli derinlik öncelikli arama

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

Sezgi

paint(r, c) işlevini yazın; bu işlev tek bir küçük iş yapar: (r, c) görüntünün içindeyse ve hâlâ eski renge sahipse, ona yeni rengi verir ve kendisini dört komşu piksel için çağırır. Başlangıç pikselinde yapılan tek bir çağrı tüm bölgeye yayılır, çünkü bölgedeki her piksel eski renkli piksellerden oluşan bir yol aracılığıyla başlangıç noktasına bağlıdır ve çağrılar bu yolu izler.

Dört çağrıdan önce pikseli boyamak, yayılmanın döngüye girmesini engeller: bir komşu boyanmış bir piksele geri çağrı yaptığında renk artık eşleşmez ve çağrı hemen geri döner. Bu yalnızca yeni renk eski renkten farklı olduğunda işe yarar; bu yüzden önce bunu kontrol edin ve renkler eşitse görüntüyü değiştirmeden döndürün.

İş miktarı O(m × n) olur, ancak zayıf nokta çağrı yığınıdır. Özyineleme, izlediği yol kadar derine iner. 80 × 80 boyutundaki bir görüntüde, tek piksel genişliğinde kıvrılan bir yol yaklaşık 3.200 piksel uzunluğundadır; bu nedenle çağrılar yaklaşık 3.200 kat iç içe geçer. Python varsayılan olarak 1.000 çağrı sınırında durur ve hata verir; bu yüzden bu yaklaşım en büyük testleri tamamlayamaz. Diğer diller daha derin çağrılara izin verir, ancak daha büyük bir görüntü onların çağrı yığınını da tüketir.

Algoritma

old = image[sr][sc] değerini oku. old, color değerine eşitse görüntüyü döndür.
paint(r, c) işlevini tanımla: (r, c) görüntünün dışındaysa veya rengi old değilse geri dön.
Aksi takdirde image[r][c] = color olarak ayarla ve üstteki, alttaki, soldaki ve sağdaki pikseller için paint işlevini çağır.
paint(sr, sc) işlevini çağır ve görüntüyü döndür.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

Örtük bir yığınla derinlik öncelikli arama

Sezgi

Aynı dolaşımı yap, ancak ziyaret edilecek pikselleri çağrı yığını yerine kendi yığınında tut. Başlangıç pikselini boya ve yığına ekle. Bir pikseli yığından çıkar, dört komşusuna bak ve görüntünün içinde olup hâlâ eski renkte olan her komşuyu boya ve yığına ekle. Yığın boşaldığında bölgenin tamamını boyamış olursun.

Bir pikseli yığından çıkardığında değil, yığına eklediğinde boya. Boyanmış bir piksel artık eski renkte olmadığından, renk kontrolü aynı zamanda ziyaret edilip edilmediğini kontrol eder: hiçbir piksel yığına iki kez girmez ve ayrı bir işaretleme ızgarasına gerek kalmaz. Özyinelemeli sürümde olduğu gibi, bunun için yeni rengin eski renkten farklı olması gerekir; bu yüzden renkler eşitse görüntüyü değiştirmeden döndür.

Bölgedeki her piksel yığına bir kez eklenir ve dört komşusu kontrol edilir; dolayısıyla süre O(m × n) olur. Yığın, bölgedeki en fazla piksel sayısı kadar eleman tutar. Normal bellekte yer kapladığından, özyinelemeli sürümün çağrı yığını yetersiz kalırken kıvrımlı bir 3,200 piksellik bölgeyi işlemek sorun olmaz.

Algoritma

old = image[sr][sc] ifadesini oku. old, color değerine eşitse görüntüyü döndür.
(sr, sc) pikselini boya ve bir yığına ekle.
Bir pikseli yığından çıkar ve dört komşusuna bak.
Görüntünün içinde bulunan ve rengi old olan her komşuyu boya ve yığına ekle.
Yığın boş olduğunda görüntüyü döndür.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu aynı renk durumundan, görüntünün dışına çıkmaktan veya uzun bir bölgede özyineleme kullanmaktan kaynaklanır.

color değerinin başlangıç rengine eşit olduğu durumu unutmak. Boyama hiçbir şeyi değiştirmez; bu nedenle rengi ziyaret işareti olarak kullanan bir arama, aynı pikselleri sonsuza kadar yığına ekler.
Boyadıktan sonra image[sr][sc] değerini okumak. Önce eski rengi kaydedin; yoksa her komşuyu yeni renkle karşılaştırırsınız.
Köşegen komşuları saymak. Yalnızca köşelerinden temas eden pikseller birbirine bağlı değildir.
Bir komşunun rengini, görüntünün içinde olup olmadığını kontrol etmeden denetlemek. Önce 0 ≤ row < rows ve 0 ≤ col < cols koşullarını sınayın.
Büyük bir görüntüde özyineleme kullanmak. 80 × 80 boyutundaki bir görüntüde bir piksel genişliğindeki yol yaklaşık 3.200 piksel uzunluğundadır; bu, Python'un özyineleme sınırını aşacak kadar derindir.
Görüntünün tamamındaki eski renkteki her pikseli boyamak. Başlangıç noktasından kopuk olan bu renkteki pikseller renklerini korumalıdır.

Sıkça sorulan sorular4

Flood Fill algoritmasının zaman karmaşıklığı nedir?

m satır ve n sütundan oluşan bir görüntü için O(m × n). Bölgedeki her piksel yığına bir kez eklenir ve dört komşusuna bakar; bölgenin dışındaki piksellere ise yalnızca komşu olarak bakılır. Görüntünün tamamı tek bir bölge olduğunda yığın en fazla m × n piksel tutabilir.

Flood Fill için BFS mi yoksa DFS mi kullanmalısınız?

İkisi de işe yarar ve her ikisi de O(m × n) zaman alır. Bölgeyi hangi sırayla ziyaret ettiğiniz fark etmez; bu yüzden bir kuyruk (önce genişlik) ve bir yığın (önce derinlik) aynı pikselleri boyar. Dilinizde yazması daha kısa olanı seçin ve büyük görüntülerde özyinelemeden kaçının.

Yeni renk eski renkle aynı olduğunda Flood Fill neden sonsuz döngüye girer?

Olağan çözüm, “hâlâ eski renkte olmayı” “henüz ziyaret edilmemiş olmak” şeklinde ele alır. Yeni renk eski renkle aynı olduğunda bir pikseli boyamak onu değiştirmez; bu nedenle komşuları onu tekrar yığına ekler ve arama hiç bitmez. Önce bu durumu kontrol edip görüntüyü döndürmek sorunu çözer; değişmemiş görüntü doğru yanıttır.

Flood Fill özyinelemeli olarak çözülebilir mi?

Evet, bir pikseli boyayan ve eski rengin her komşusunda kendini çağıran bir işlev doğrudur. Risk derinliktir: özyineleme, aramanın izlediği en uzun yol kadar derine gider; kıvrımlı bir bölgede bu, binlerce çağrı olabilir. Açık bir yığın, bu sınır olmadan aynı işi yapar.

Python

def floodFill(image, sr, sc, color):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

Beklenen

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]