. Teka-teki Gelongsor

773. Teka-teki Gelongsor

Kesukaran: Sukar

Topik: Tatasusunan, Keluasan-Carian Pertama, Matriks

Pada papan 2 x 3, terdapat lima jubin yang dilabelkan dari 1 hingga 5, dan segi empat sama kosong diwakili oleh 0. A gerakan terdiri daripada memilih 0 dan nombor bersebelahan 4 arah dan menukarnya .

Keadaan papan diselesaikan jika dan hanya jika papan itu [[1,2,3],[4,5,0]].

Memandangkan papan papan teka-teki, kembalikan bilangan paling sedikit pergerakan yang diperlukan supaya keadaan papan itu diselesaikan. Jika keadaan lembaga tidak dapat diselesaikan, kembalikan -1.

Contoh 1:

• Input: papan = [[1,2,3],[4,0,5]]
• Output: 1
• Penjelasan: Tukar 0 dan 5 dalam satu pergerakan.

Contoh 2:

• Input: papan = [[1,2,3],[5,4,0]]
• Output: -1
• Penjelasan: Tiada bilangan pergerakan akan membuat papan diselesaikan.

Contoh 3:

• Input: papan = [[4,1,2],[5,0,3]]
• Output: 5
• Penjelasan: 5 ialah bilangan pergerakan terkecil yang menyelesaikan papan.
  • Contoh laluan:
  • Selepas langkah 0: [[4,1,2],[5,0,3]]
  • Selepas langkah 1: [[4,1,2],[0,5,3]]
  • Selepas langkah 2: [[0,1,2],[4,5,3]]
  • Selepas langkah 3: [[1,0,2],[4,5,3]]
  • Selepas langkah 4: [[1,2,0],[4,5,3]]
  • Selepas langkah 5: [[1,2,3],[4,5,0]]

Kekangan:

• papan.panjang == 2
• papan[i].panjang == 3
• 0 <= papan[i][j] <= 5
• Setiap papan nilai[i][j] adalah unik.

Petunjuk:

1. Lakukan carian luas-pertama, di mana nod adalah papan teka-teki dan tepi adalah jika dua papan teka-teki boleh diubah menjadi satu sama lain dengan satu gerakan.

Penyelesaian:

Kami boleh menggunakan algoritma Breadth-First Search (BFS). Ideanya adalah untuk meneroka semua kemungkinan konfigurasi papan bermula dari keadaan awal yang diberikan, satu langkah pada satu masa, sehingga kita mencapai keadaan yang diselesaikan.

Pendekatan:

1. Breadth-First Search (BFS):

   • BFS sesuai di sini kerana kami sedang mencari jalan terpendek ke keadaan yang diselesaikan.
   • Setiap konfigurasi papan boleh dianggap sebagai nod, dan tepi antara nod mewakili pergerakan yang sah apabila jubin 0 ditukar dengan jubin bersebelahan.
   • BFS akan meneroka konfigurasi papan peringkat demi tahap, memastikan kami mencapai keadaan yang diselesaikan dengan bilangan pergerakan minimum.

2. Perwakilan Negeri:

   • Kami akan mewakili papan sebagai rentetan (untuk perbandingan dan penyimpanan yang lebih mudah).
   • Keadaan yang diselesaikan ialah "123450" kerana ia merupakan perwakilan linear papan [[1,2,3],[4,5,0]].

3. Peralihan Negeri:

   • Dari setiap negeri, jubin 0 boleh bertukar dengan salah satu daripada 4 jirannya (atas, bawah, kiri, kanan), jika ia berada dalam sempadan papan.

4. Menjejaki Negeri yang Dilawati:

   • Kita perlu menjejaki negeri yang dilawati untuk mengelakkan kitaran dan pengiraan berlebihan.

5. Menyemak untuk Keadaan Selesai:

   • Jika pada bila-bila masa konfigurasi papan sepadan dengan keadaan yang diselesaikan, kami mengembalikan bilangan pergerakan yang diperlukan untuk sampai ke sana.

6. Mengendalikan Kes Mustahil:

   • Jika BFS selesai dan kami tidak menjumpai keadaan yang telah diselesaikan, ini bermakna mustahil untuk menyelesaikan teka-teki, dan kami mengembalikan -1.

Mari laksanakan penyelesaian ini dalam PHP: 773. Teka-teki Gelongsor

  
  
  Penjelasan:




Persediaan Awal: Kami mulakan dengan menukar papan 2D kepada rentetan 1D untuk manipulasi yang lebih mudah.

Pelaksanaan BFS: Kami membuat baris gilir keadaan awal papan bersama-sama dengan kiraan pergerakan (bermula dari 0). Dalam setiap lelaran BFS, kami meneroka kemungkinan pergerakan (berdasarkan kedudukan jubin 0), menukar 0 dengan jubin bersebelahan dan beratur keadaan baharu.

Negeri Dilawati: Kami menggunakan kamus untuk menjejaki negeri lembaga yang dilawati untuk mengelak daripada melawat semula dan bergelung kembali ke negeri yang sama.

Pengesahan Tepi: Kami menyemak sama ada sebarang pergerakan kekal dalam sempadan grid 2x3, terutamanya memastikan tiada pergerakan haram yang membungkus grid (seperti bergerak ke kiri di tepi kiri atau kanan di tepi kanan). 

Keputusan Pulangan: Jika kita mencapai keadaan sasaran, kita mengembalikan bilangan pergerakan. Jika BFS selesai dan kami tidak mencapai sasaran, kami kembali -1.



  
  
  Kerumitan Masa:




Kerumitan BFS: Kerumitan masa BFS ialah O(N), dengan N ialah bilangan keadaan papan unik. Untuk teka-teki ini, terdapat paling banyak 6! (720) konfigurasi yang mungkin.



  
  
  Kerumitan Ruang:



Kerumitan ruang juga O(N) disebabkan oleh storan yang diperlukan untuk baris gilir dan negeri yang dilawati.


Penyelesaian ini sepatutnya cukup cekap memandangkan kekangan.

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 . Teka-teki Gelongsor. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!