Bilangan Hari Minimum untuk Memutuskan Sambungan Pulau

1568. Bilangan Hari Minimum untuk Memutuskan Sambungan Pulau

Kesukaran: Sukar

Topik: Tatasusunan, Depth-First Search, Breadth-First Search, Matriks, Komponen Sangat Bersambung

Anda diberi grid grid perduaan m x n di mana 1 mewakili tanah dan 0 mewakili air. Pulau ialah kumpulan bersambung 4 arah (mendatar atau menegak) maksimum bagi 1.

Grid dikatakan disambungkan jika kita mempunyai tepat satu pulau, sebaliknya dikatakan terputus.

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

Kembali bilangan minimum hari 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 terputus. Tukar grid darat[1][1] dan grid[0][2] kepada air dan dapatkan 2 pulau terputus.

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. Jika tidak, kembalikan 2.
4. Kami boleh memutuskan sambungan grid dalam masa paling lama 2 hari.

Penyelesaian:

Kita perlu mempertimbangkan langkah berikut:

Langkah-langkah untuk Menyelesaikan Masalah:

1. Semak Ketersambungan Permulaan: 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, kembalikan 2.

Fungsi Utama:

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

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

  
  
  Penjelasan:




Fungsi minDays() mengendalikan logik utama.

countIslands() mengira bilangan pulau yang ada menggunakan DFS.

dfs() ialah fungsi rekursif untuk meneroka grid dan menandakan sel tanah yang dilawati.


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 Bilangan Hari Minimum untuk Memutuskan Sambungan Pulau. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!