Kira Sel Tidak Terkawal dalam Grid

2257. Kira Sel Tidak Berkawal dalam Grid

Kesukaran: Sederhana

Topik: Tatasusunan, Matriks, Simulasi

Anda diberi dua integer m dan n mewakili grid 0-diindeks m x n. Anda juga diberikan dua pengawal tatasusunan integer 2D dan dinding di mana pengawal[i] = [baris_i, col_i] dan dinding[j] = [baris_j, col_j] mewakili kedudukan i^th guard dan j^th wall masing-masing.

Seorang pengawal boleh melihat setiap sel dalam empat arah mata angin (utara, timur, selatan atau barat) bermula dari kedudukan mereka melainkan dihalang oleh dinding atau pengawal lain. Sebuah sel dijaga jika terdapat sekurang-kurangnya seorang pengawal yang dapat melihatnya.

Kembalikan bilangan sel tidak berpenghuni yang tidak dijaga.

Contoh 1:

• Input: m = 4, n = 6, pengawal = [[0,0],[1,1],[2,3]], dinding = [[0,1],[2, 2],[1,4]]
• Output: 7
• Penjelasan: Sel yang dikawal dan tidak dikawal ditunjukkan dalam warna merah dan hijau masing-masing dalam rajah di atas.
  • Terdapat sejumlah 7 sel yang tidak dikawal, jadi kami mengembalikan 7.

Contoh 2:

• Input: m = 3, n = 3, pengawal = [[1,1]], dinding = [[0,1],[1,0],[2,1],[1, 2]]
• Output: 4
• Penjelasan: Sel yang tidak dikawal ditunjukkan dalam warna hijau dalam rajah di atas.
  • Terdapat sejumlah 4 sel yang tidak dikawal, jadi kami mengembalikan 4.

Kekangan:

• 1 <= m, n <= 10⁵
• 2 <= m * n <= 10⁵
• 1 <= pengawal.panjang, dinding.panjang <= 5 * 10⁴
• 2 <= pengawal.dinding panjang.panjang <= m * n
• pengawal[i].panjang == dinding[j].panjang == 2
• 0 <= baris_i, baris_j < m
• 0 <= col_i, col_j < n
• Semua jawatan dalam pengawal dan dinding adalah unik.

Petunjuk:

1. Buat tatasusunan 2D untuk mewakili grid. Bolehkah anda menandakan jubin yang boleh dilihat oleh pengawal?
2. Lelaran di atas pengawal, dan untuk setiap satu daripada 4 arah, majukan jubin semasa dan tandai jubin. Bilakah anda harus berhenti memajukan?

Penyelesaian:

Kita perlu menandakan sel yang dikawal oleh sekurang-kurangnya seorang pengawal. Pengawal boleh melihat dalam empat arah mata angin (utara, selatan, timur, dan barat), tetapi penglihatan mereka disekat oleh dinding. Kita boleh mensimulasikan proses ini dan mengira bilangan sel yang tidak dikawal.

Pendekatan:

1. Buat grid: Kami boleh mewakili grid sebagai tatasusunan 2D di mana setiap sel boleh menjadi dinding, pengawal atau kosong.
2. Tandai sel yang dikawal: Untuk setiap pengawal, lelar ke empat arah (utara, selatan, timur, barat) dan tandakan semua sel yang boleh dilihatnya, berhenti apabila kita bertemu dengan dinding atau pengawal lain.
3. Kira sel yang tidak dikawal: Selepas menandakan sel yang dikawal, kira berapa banyak sel yang tidak dikawal dan bukan dinding.

Langkah-langkah:

1. Permulaan Grid: Buat tatasusunan 2D untuk mewakili grid. Tandai sel dengan dinding, pengawal dan kawasan berkawal semasa kami mengulangi.

2. Simulasi Perlindungan Pengawal:

   • Pengawal boleh melihat dalam empat arah (utara, selatan, timur, barat).
   • Tandai sel yang dikawal oleh setiap pengawal sehingga bertemu dengan dinding atau pengawal lain.

3. Mengira Sel Tidak Berkawal: Selepas memproses semua pengawal, kira sel yang bukan dinding, pengawal, mahupun berkawal.

Mari laksanakan penyelesaian ini dalam PHP: 2257. Kira Sel Tidak Berkawal dalam Grid

  
  
  Penjelasan:




Permulaan:


Grid dimulakan dengan 0 untuk sel kosong. Dinding dan pengadang ditanda dengan pemalar unik.



Simulasi Pengawal:


Untuk setiap pengawal, simulasikan pergerakan dalam keempat-empat arah, tandakan sel sebagai dikawal sehingga melanggar dinding atau pengawal lain.



Mengira Sel Tidak Terjaga:

Selepas memproses semua pengawal, lelaran melalui grid dan kira sel yang masih ditandakan sebagai 0.





  
  
  Prestasi:



Kerumitan masa: O(m x n g x d), dengan g ialah bilangan pengawal dan d  ialah bilangan sel dalam arah yang boleh dilalui oleh setiap pengawal.
Kerumitan ruang: O(m x n) untuk grid.



  
  
  Kerumitan Masa:




Pengamatan grid: _O(m * n), di mana _m dan n ialah dimensi grid.

Menandai penglihatan pengawal: Setiap pengawal menyemak paling banyak panjang baris atau lajur dalam empat arah. Jadi, bagi setiap pengawal, ia adalah O(m n).

Mengira sel yang tidak dikawal: O(m * n).


Oleh itu, kerumitan keseluruhan ialah O(m * n), yang cekap memandangkan kekangan masalah.


  
  
  Kes Tepi:



Jika tiada pengawal atau dinding wujud, seluruh grid akan tidak dikawal.
Jika semua sel sama ada dikawal atau berdinding, hasilnya akan menjadi 0 sel yang tidak dikawal.


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 Kira Sel Tidak Terkawal dalam Grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!