Bilangan Hari Minimum untuk Memutuskan Sambungan Pulau

1568. Bilangan Hari Minimum untuk Memutuskan Pulau

Kesukaran:Sukar

Topik:Tatasusunan, Carian Pertama Kedalaman, Carian Luas-Pertama, Matriks, Komponen Bersambung Kuat

Anda diberi grid grid binari m x n di mana 1 mewakili tanah dan 0 mewakili air.pulauialah kumpulan maksima4 arah(mendatar atau menegak) bersambung 1.

Grid itu dikatakanbersambungjika kita adatepat satu pulau, sebaliknya dikatakanterputus.

Dalam satu hari, kita dibenarkan menukar **** mana-mana sel tanah tunggal (1) kepada sel air (0).

Kembalijumlah hari minimum untuk memutuskan sambungan grid.

Contoh 1:

• Input:grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• Output:2
• Penjelasan:Kami memerlukan sekurang-kurangnya 2 hari untuk mendapatkan grid yang terputus. Tukar grid darat[1][1] dan grid[0][2] kepada air dan dapatkan 2 pulau terputus sambungan.

Contoh 2:

• Input:grid = [[1,1]]
• Output:2
• Penjelasan:Grid air penuh juga terputus ([[1,1]] -> [[0,0]]), 0 pulau.

Kekangan:

• m == grid.panjang
• n == grid[i].panjang
• 1 <= m, n <= 30
• grid[i][j] ialah sama ada 0 atau 1.

Petunjuk:

1. Kembalikan 0 jika grid sudah terputus.
2. Kembali 1 jika menukar satu tanah kepada air putuskan pulau itu.
3. Kalau tak balik 2.
4. Kami boleh memutuskan sambungan grid dalam masa paling lama 2 hari.

Penyelesaian:

Kita perlu mempertimbangkan langkah-langkah berikut:

Langkah-langkah untuk Menyelesaikan Masalah:

1. Semak Ketersambungan Awal: Mula-mula, semak sama ada grid sudah terputus sambungan dengan menentukan sama ada terdapat lebih daripada satu pulau dalam grid. Jika ia sudah terputus, kembalikan 0.

2. Semak Jika Penyingkiran Tunggal Memutuskan Sambungan Pulau: Lelaran melalui setiap sel grid. Tukar sel dari 1 kepada 0 buat sementara waktu (jika 1) dan semak sama ada grid terputus sambungan dengan mengira bilangan pulau. Jika menukar sel tunggal memutuskan sambungan pulau, kembalikan 1.

3. Pemutus Sambungan Dua Hari: Jika tiada penukaran sel tunggal memutuskan sambungan pulau, maka grid boleh diputuskan sambungan dengan menukar mana-mana dua sel darat bersebelahan. Oleh itu, kembali 2.

Fungsi Utama:

• DFS (Depth-First Search)untuk mencari dan mengira pulau.
• isConnecteduntuk menyemak sama ada grid disambungkan.

Mari kita laksanakan penyelesaian ini dalam PHP:1568. Bilangan Hari Minimum untuk Memutuskan Pulau

        
Penjelasan:
        

         
FungsiminDays()mengendalikan logik utama.
         
countIslands()mengira bilangan pulau yang ada menggunakan DFS.
         
dfs()ialah fungsi rekursif untuk meneroka grid dan menandakan sel tanah yang dilawati.
        
Hubungi Pautan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna buat saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
        

         
LinkedIn
         
GitHub
        
Atas ialah kandungan terperinci Bilangan Hari Minimum untuk Memutuskan Sambungan Pulau. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!