Flood Fill
Gambar adalah grid bilangan bulat, dengan setiap bilangan menunjukkan warna satu piksel. Kamu mendapatkan gambar dalam bentuk list baris, piksel awal pada baris sr dan kolom sc, serta color baru. Warnai ulang wilayah yang memuat piksel awal: setiap piksel yang warnanya sama dengan piksel awal dan dapat kamu jangkau darinya dengan melangkah ke atas, bawah, kiri, atau kanan melalui piksel dengan warna yang sama. Kembalikan gambar setelah diwarnai ulang.
Fungsi
- imageinteger-2d-array
- gambar sebagai list yang berisi baris, satu angka untuk setiap piksel
- srinteger
- baris piksel awal, dihitung mulai dari 0
- scinteger
- kolom piksel awal, dihitung dari 0
- colorinteger
- warna baru untuk wilayah tersebut
- Mengembalikaninteger-2d-array
- gambar setelah wilayah digambar ulang
Batasan
1 ≤ image.length ≤ 801 ≤ image[i].length ≤ 80- Setiap baris memiliki panjang yang sama.
0 ≤ image[i][j], color ≤ 655350 ≤ sr < image.lengthdan0 ≤ sc < image[0].length
Contoh
- Input
- image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
- Output
- [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
- Penjelasan
- Titik awal memiliki warna 1. Ketujuh angka 1 terhubung ke titik awal melalui angka 1 yang berbagi sisi, ke bawah sepanjang kolom kiri, ke kanan sepanjang baris bawah, lalu ke atas sepanjang tepi kanan, sehingga semuanya menjadi 5. Kedua angka 0 tetap memiliki warnanya.
- Input
- image = [[3, 3, 3], [3, 7, 3], [3, 3, 3]]sr = 1sc = 1color = 7
- Output
- [[3, 3, 3], [3, 7, 3], [3, 3, 3]]
- Penjelasan
- Titik awal sudah memiliki warna 7, jadi mewarnai wilayahnya dengan warna 7 tidak mengubah apa pun, dan gambar kembali seperti semula.
- Input
- image = [[2, 2, 4, 4], [4, 2, 2, 4], [4, 4, 2, 2]]sr = 2sc = 3color = 9
- Output
- [[9, 9, 4, 4], [4, 9, 9, 4], [4, 4, 9, 9]]
- Penjelasan
- Angka 2 membentuk tangga dari sudut kanan bawah ke sudut kiri atas, setiap anak tangga berbagi satu sisi dengan anak tangga berikutnya, sehingga semuanya berubah menjadi 9. Angka 4 membentuk dua bagian terpisah dan warnanya tetap.
Pertanyaan lanjutan
Bagaimana solusi kamu akan berubah jika piksel yang hanya bersentuhan di sudut juga dianggap terhubung?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Piksel mana saja yang bisa berubah? Hanya piksel yang memiliki warna sama dengan piksel awal, dan hanya jika ada jalur dengan warna tersebut yang menghubungkannya ke piksel awal.
Anggap setiap piksel sebagai simpul dan hubungkan dua piksel jika keduanya berbagi sisi dan memiliki warna awal. Wilayahnya mencakup semua yang dapat kamu jangkau dari titik awal, jadi pencarian graf apa pun dapat menemukannya.
Simpan tumpukan piksel yang masih perlu diperiksa. Warnai piksel saat kamu menambahkannya ke tumpukan, sehingga piksel yang sudah diwarnai tidak lagi cocok dan tidak akan ditambahkan lagi. Periksa terlebih dahulu apakah warna baru sama dengan warna lama.
Solusi
Anggap piksel sebagai simpul, lalu hubungkan dua piksel dengan warna awal jika keduanya berbagi sisi. Wilayahnya adalah bagian terhubung yang mencakup titik awal, dan pencarian apa pun dari titik awal yang hanya menelusuri warna tersebut akan menemukannya. Perhatikan warna baru yang sama dengan warna lama, serta wilayah berliku panjang yang menyebabkan rekursi meluap.
Pencarian mendalam rekursif
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
paint(r, c) mewarnai sebuah piksel di dalam gambar yang masih memiliki warna lama, lalu memanggil dirinya sendiri pada keempat piksel tetangganya. Setiap piksel di wilayah tersebut terhubung ke titik awal melalui jalur piksel berwarna lama, dan pemanggilan fungsi mengikuti jalur itu. Mewarnai sebelum pemanggilan fungsi mencegah penyebaran berputar kembali, karena piksel yang sudah diwarnai tidak lagi cocok. Cara ini hanya berhasil jika kedua warna berbeda, jadi kembalikan eksekusi lebih awal jika warnanya sama.
Rekursi berjalan sedalam jalur yang diikutinya. Ular selebar satu piksel yang melewati gambar berukuran 80 × 80 panjangnya sekitar 3.200 piksel, jadi pemanggilan fungsi bersarang hingga sekitar 3.200 tingkat, dan gambar yang lebih besar akan menghabiskan tumpukan pemanggilan.
Algoritma
- Baca
old = image[sr][sc]. Jikaoldsama dengancolor, kembalikan image. - Definisikan
paint(r, c): kembalikan jika(r, c)berada di luar image atau warnanya bukanold. - Jika tidak, atur
image[r][c] = colordan panggilpaintpada piksel di atas, bawah, kiri, dan kanan. - Panggil
paint(sr, sc)dan kembalikan image.
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 imagePencarian depth-first dengan stack eksplisit
Intuisi
Lakukan penelusuran yang sama dengan stack milikmu sendiri, bukan call stack. Warnai piksel saat kamu mendorongnya ke stack, bukan saat kamu mengeluarkannya. Pemeriksaan warna sekaligus berfungsi sebagai pemeriksaan kunjungan: tidak ada piksel yang masuk ke stack dua kali, dan kamu tidak memerlukan grid penanda terpisah.
Setiap piksel di wilayah tersebut didorong sekali dan memeriksa empat tetangganya, jadi waktunya adalah O(m × n). Stack berada di memori biasa, jadi ular sepanjang 3,200 piksel bukan masalah.
Algoritma
- Baca
old = image[sr][sc]. Jikaoldsama dengancolor, kembalikan image. - Warnai
(sr, sc)dan masukkan ke dalam stack. - Ambil satu pixel dari stack, lalu periksa keempat tetangganya.
- Untuk setiap tetangga di dalam image yang warnanya
old, warnai dan masukkan ke dalam stack. - Saat stack kosong, kembalikan image.
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
Jebakan dan kasus tepi
- Membaca
image[sr][sc]setelah kamu mewarnainya. Simpan warna lama terlebih dahulu, atau setiap tetangga akan dibandingkan dengan warna baru. - Menghitung tetangga diagonal. Piksel yang hanya bersentuhan di sudut tidak terhubung.
- Memeriksa warna tetangga sebelum memastikan bahwa posisinya berada di dalam gambar. Uji
0 ≤ row < rowsdan0 ≤ col < colsterlebih dahulu. - Menggunakan rekursi di Python, yang batas default 1.000 pemanggilannya akan berhenti pada jalur berkelok di atas.
- Mewarnai setiap piksel dengan warna lama di seluruh gambar. Piksel dengan warna tersebut yang terputus dari titik awal akan tetap memiliki warnanya.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Flood Fill?
O(m × n) untuk gambar dengan m baris dan n kolom. Setiap piksel di wilayah tersebut dimasukkan ke stack satu kali dan memeriksa empat tetangganya, sedangkan piksel di luar wilayah tersebut hanya diperiksa sebagai tetangga. Stack menampung hingga m × n piksel saat seluruh gambar merupakan satu wilayah.
Apakah kamu sebaiknya menggunakan BFS atau DFS untuk Flood Fill?
Keduanya bekerja dalam waktu O(m × n). Wilayahnya sama dalam urutan kunjungan apa pun, jadi queue (pencarian melebar) dan stack (pencarian mendalam) mewarnai piksel yang sama. Pilih yang lebih singkat untuk ditulis, dan hindari rekursi pada gambar berukuran besar.
Mengapa Flood Fill mengalami perulangan tanpa akhir ketika warna baru sama dengan warna lama?
Solusi yang biasa menganggap "masih memiliki warna lama" berarti "belum dikunjungi". Ketika warna baru sama dengan warna lama, pewarnaan tidak mengubah apa pun, sehingga sel-sel tetangga terus saling mendorong kembali ke tumpukan tanpa henti. Kembalikan gambar tanpa perubahan dalam kasus itu, karena gambar tersebut sudah merupakan jawaban yang benar.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def floodFill(image, sr, sc, color):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]] sr = 0 sc = 0 color = 5
Output yang diharapkan
[[5, 5, 0], [5, 0, 5], [5, 5, 5]]