Count Sub Islands

1905. Count Sub Islands

Kesukaran: Sederhana

Topik: Tatasusunan, Depth-First Search, Breadth-First Search, Union Find, Matriks

Anda diberi dua m x n matriks binari grid1 dan grid2 yang mengandungi hanya 0 (mewakili air) dan 1 (mewakili tanah). Pulau ialah sekumpulan 1 yang bersambung 4 arah (mendatar atau menegak). Mana-mana sel di luar grid dianggap sebagai sel air.

Pulau dalam grid2 dianggap pulau kecil jika terdapat pulau dalam grid1 yang mengandungi semua sel yang membentuk pulau ini dalam grid2 .

Kembalikan bilangan pulau dalam grid2 yang dianggap pulau kecil.

Contoh 1:

• Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1, 0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[ 0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
• Output: 3
• Penjelasan:
  • Dalam gambar di atas, grid di sebelah kiri ialah grid1 dan grid di sebelah kanan ialah grid2.
  • 1s berwarna merah dalam grid2 adalah yang dianggap sebagai sebahagian daripada sub-pulau. Terdapat tiga sub-pulau.

Contoh 2:

• Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1, 1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[ 0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
• Output: 2
• Penjelasan:
  • Dalam gambar di atas, grid di sebelah kiri ialah grid1 dan grid di sebelah kanan ialah grid2.
  • 1s berwarna merah dalam grid2 adalah yang dianggap sebagai sebahagian daripada sub-pulau. Terdapat dua sub-pulau.

Kekangan:

• m == grid1.panjang == grid2.panjang
• n == grid1[i].panjang == grid2[i].panjang
• 1 <= m, n <= 500
• grid1[i][j] dan grid2[i][j] adalah sama ada 0 atau 1.

Petunjuk:

1. Mari kita gunakan timbunan limpah untuk mengulangi pulau-pulau grid kedua
2. Mari kita ambil perhatian bahawa jika semua sel di pulau dalam grid kedua jika ia diwakili oleh tanah dalam grid pertama maka ia disambungkan justeru menjadikan pulau itu sub-pulau

Penyelesaian:

Kami akan menggunakan pendekatan Depth-First Search (DFS) untuk meneroka pulau dalam grid2 dan menyemak sama ada setiap pulau sepenuhnya terkandung dalam pulau yang sepadan dalam grid1. Begini cara kami boleh melaksanakan penyelesaian:

Langkah-langkah:

1. Melintasi Grid: Kami akan mengulangi setiap sel dalam grid2.
2. Kenal pasti Pulau dalam grid2: Apabila kami menemui sel darat (1) dalam grid2, kami akan menggunakan DFS untuk meneroka seluruh pulau.
3. Semak Keadaan Sub-Pulau: Semasa melakukan DFS di pulau dalam grid2, kami akan menyemak sama ada semua sel yang sepadan dalam grid1 juga merupakan sel darat. Jika ya, pulau itu adalah sub-pulau.
4. Kira Pulau Kecil: Bagi setiap pulau dalam grid2 yang memenuhi syarat pulau kecil, kami akan menambah kiraan pulau kecil kami.

Mari kita laksanakan penyelesaian ini dalam PHP: 1905. Count Sub Islands

  
  
  Penjelasan:




Fungsi DFS: Fungsi dfs meneroka pulau dalam grid2 dan menyemak sama ada sel yang sepadan dalam grid1 adalah semua sel darat. Jika mana-mana sel dalam grid2 ialah tanah tetapi sel yang sepadan dalam grid1 ialah air, pulau dalam grid2 bukanlah sub-pulau.

Tandakan Dilawati: Semasa kami melintasi grid2, kami menandakan sel sebagai dilawati dengan menetapkannya kepada 0.

Gelung Utama: Kami mengulangi semua sel dalam grid2. Setiap kali kami menemui sel darat yang belum dilawati, kami memulakan DFS untuk menyemak sama ada ia sebahagian daripada sub-pulau.



  
  
  Kerumitan Masa:


Kerumitan masa ialah (O(m kali n)) dengan m ialah bilangan baris dan n ialah bilangan lajur. Ini kerana kami berpotensi melawat setiap sel sekali.

Penyelesaian ini harus berfungsi dengan cekap dalam kekangan yang diberikan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Count Sub Islands. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!