Komponen Bersambung dan Isian Banjir
Kira pulau dan labelkan rantau.
Komponen Bersambung dan Isian Banjir ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah Komponen Itu
Komponen bersambung ialah kumpulan nod yang semuanya boleh dicapai dari satu sama lain. Sesebuah graf boleh mengandungi beberapa kumpulan yang berasingan. 🧩
Mengira Komponen
Untuk mengira komponen, jalankan penelusuran dari setiap nod yang belum dilawati. Setiap permulaan baharu menandakan satu kumpulan baharu yang lengkap.
Ulang Melalui Semua Nod
Telusuri nod daripada 1 hingga n. Apabila anda menemui nod yang masih belum dilawati, anda telah menemukan komponen baharu untuk diteroka.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Satu Penelusuran bagi Setiap Kumpulan
BFS atau DFS dalaman itu menandakan seluruh komponen sebagai telah dilawati, jadi gelung luaran melangkaunya pada pusingan seterusnya.
Grid Juga Graf
Grid dua dimensi ialah graf tersembunyi: setiap sel ialah nod yang bersambung dengan jirannya. Ini membuka idea klasik pengisian kawasan. 🗺️
Empat Arah
Dari sesuatu sel, anda biasanya bergerak ke atas, ke bawah, ke kiri dan ke kanan. Simpan pergerakan itu sebagai vektor arah supaya kod kekal kemas.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Kekal dalam Grid
Sebelum bergerak, semak bahawa baris dan lajur baharu berada dalam sempadan. Jika semakan ini dilangkau, ralat indeks atau jawapan yang salah boleh berlaku.
if 0 <= nr < rows and 0 <= nc < cols:
passIsian Banjir Satu Kawasan
Isian banjir bermula pada satu sel dan merebak ke setiap sel bersambung yang mempunyai jenis sama, seperti alat baldi cat.
Mengira Pulau
Untuk mengira pulau, imbas grid; pada setiap sel daratan baharu, lakukan isian banjir pada seluruh pulaunya dan tambah satu pada kiraan.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Menandai Kawasan
Anda boleh menyimpan penanda bagi setiap sel semasa isian. Kemudian, Anda boleh mengetahui serta-merta kawasan yang dimiliki oleh mana-mana sel.
Linear Mengikut Saiz Grid
Setiap sel dilawati sekali, jadi isian banjir pada grid berjalan dalam O(baris kali lajur). Ini dapat memenuhi had pertandingan dengan selesa.
Semakan Pantas
Bagaimanakah Anda mengira komponen bersambung?
Imbas Kembali
Anda mengira komponen dengan melintasi dari setiap nod yang belum dilawati, dan menggunakan isian banjir pada grid untuk menandai kawasan serta mengira pulau. 🎉
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Komponen Bersambung dan Isian Banjir” percuma?
Ya — teks penuh “Komponen Bersambung dan Isian Banjir” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Komponen Bersambung dan Isian Banjir”?
Kira pulau dan labelkan rantau. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Komponen Bersambung dan Isian Banjir” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Senarai Kejiranan daripada Input
- BFS untuk Laluan Terpendek Tanpa Pemberat
- DFS, Rekursi dan Timbunan Beriterasi
- Komponen Bersambung dan Isian Banjir