. Kebanyakan Batu Dialih Keluar dengan Baris atau Lajur yang Sama

947. Kebanyakan Batu Dialih Keluar dengan Baris atau Lajur yang Sama

Kesukaran:Sederhana

Topik:Jadual Hash, Carian Pertama Kedalaman, Carian Kesatuan, Graf

Pada satah 2D, kami meletakkan n batu pada beberapa titik koordinat integer. Setiap titik koordinat mungkin mempunyai paling banyak satu batu.

Batu boleh dialihkan jika ia berkongsi sama adabaris yang sama atau lajur yang samadengan batu lain yang belum dialihkan.

Memandangkan susunan batu dengan panjang n di mana batu[i] = [xi, yi] mewakili lokasi batu i^th, kembalikanbilangan batu terbesar yang boleh dialihkan.

Contoh 1:

• Input:batu = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
• Output:5
• Penjelasan:Salah satu cara untuk membuang 5 batu adalah seperti berikut:
  1. Alih keluar batu [2,2] kerana ia berkongsi baris yang sama seperti [2,1].
  2. Alih keluar batu [2,1] kerana ia berkongsi lajur yang sama dengan [0,1].
  3. Alih keluar batu [1,2] kerana ia berkongsi baris yang sama dengan [1,0].
  4. Alih keluar batu [1,0] kerana ia berkongsi lajur yang sama dengan [0,0].
  5. Alih keluar batu [0,1] kerana ia berkongsi baris yang sama dengan [0,0].
  6. Batu [0,0] tidak boleh dialih keluar kerana ia tidak berkongsi baris/lajur dengan batu lain yang masih berada di atas kapal terbang.

Contoh 2:

• Input:batu = [[0,0],[0,2],[1,1],[2,0],[2,2]]
• Output:3
• Penjelasan:Salah satu cara untuk membuat 3 gerakan adalah seperti berikut:
  1. Alih keluar batu [2,2] kerana ia berkongsi baris yang sama dengan [2,0].
  2. Alih keluar batu [2,0] kerana ia berkongsi lajur yang sama dengan [0,0].
  3. Alih keluar batu [0,2] kerana ia berkongsi baris yang sama dengan [0,0].
  4. Batu [0,0] dan [1,1] tidak boleh dialih keluar kerana ia tidak berkongsi baris/lajur dengan batu lain yang masih berada di dalam pesawat.

Contoh 3:

• Input:batu = [[0,0]]
• Output:0
• Penjelasan:[0,0] ialah satu-satunya batu pada pesawat, jadi anda tidak boleh mengeluarkannya.

Kekangan:

• 1 <= batu.panjang <= 1000
• 0 <= x_i, y_i<= 10⁴
• Tiada dua batu berada pada titik koordinat yang sama.

Penyelesaian:

Kami boleh melaksanakan penyelesaian menggunakan pendekatan Depth-First Search (DFS). Ideanya adalah untuk mempertimbangkan batu yang disambungkan oleh baris atau lajur sebagai sebahagian daripada komponen yang disambungkan yang sama. Sebaik sahaja anda menemui semua komponen yang disambungkan, bilangan maksimum batu yang boleh dialihkan ialah jumlah bilangan batu tolak bilangan komponen yang disambungkan.

Mari kita laksanakan penyelesaian ini dalam PHP:947. Kebanyakan Batu Dialih Keluar dengan Baris atau Lajur yang Sama

        
Penjelasan:
        

         
Fungsi DFS:
          

           
Fungsi dfs digunakan untuk meneroka semua batu yang berada dalam komponen bersambung yang sama. Jika batu disambungkan (dalam baris atau lajur yang sama) ke batu semasa, kami melakukan DFS secara rekursif pada batu itu.
          
         
Fungsi Utama:
          

           
Kami mengulangi semua batu, dan untuk setiap batu yang belum dilawati, kami melakukan DFS untuk menandakan semua batu dalam komponen yang disambungkan yang sama.
           
Kami mengira bilangan komponen yang disambungkan dan hasilnya ialah jumlah bilangan batu tolak bilangan komponen yang disambungkan ($n - $numComponents).
          
         
Contoh Pelaksanaan:
          

           
Untuk contoh pertama, ia betul mendapati 5 batu boleh dikeluarkan, meninggalkan 1 batu yang tidak boleh dikeluarkan.
          
        
Kerumitan:
        

         
Kerumitan Masa: O(n^2) disebabkan gelung bersarang dan lintasan DFS.
         
Kerumitan Angkasa Lepas: O(n) untuk menyimpan batu yang dilawati.
        
Penyelesaian ini harus berfungsi dengan cekap dalam kekangan yang diberikan.
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang 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 . Kebanyakan Batu Dialih Keluar dengan Baris atau Lajur yang Sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!