. 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 ada baris yang sama atau lajur yang sama dengan batu lain yang belum dialihkan.

Memandangkan susunan batu dengan panjang n di mana batu[i] = [xi, yi] mewakili lokasi batu i^th, kembalikan bilangan 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 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 . Kebanyakan Batu Dialih Keluar dengan Baris atau Lajur yang Sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!