. Simulasi Robot Berjalan

874. Simulasi Robot Berjalan

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Simulasi

Robot pada satah XY tak terhingga bermula pada titik (0, 0) menghadap ke utara. Robot boleh menerima urutan tiga jenis arahan yang mungkin:

• -2: Belok kiri 90 darjah.
• -1: Belok kanan 90 darjah.
• 1 <= k <= 9: Bergerak ke hadapan k unit, satu unit pada satu masa.

Sesetengah petak grid adalah halangan. Halangan ke-1 ialah pada halangan titik grid[i] = (x_i, y_i). Jika robot itu menghadapi halangan, ia sebaliknya akan kekal di lokasi semasanya dan beralih ke arahan seterusnya.

Kembali _jarak Euclidean maksimum yang robot pernah dapat dari asal kuadrat (iaitu jika jaraknya 5, kembali 25).

Nota:

• Utara bermaksud arah +Y.
• Timur bermaksud arah +X.
• Selatan bermaksud arah -Y.
• Barat bermaksud arah -X.
• Mungkin terdapat halangan dalam [0,0].

Contoh 1:

• Input: arahan = [4,-1,3], halangan = []
• Output: 25
• Penjelasan: Robot bermula pada (0, 0):
  1. Bergerak ke utara 4 unit ke (0, 4).
  2. Belok kanan.
  3. Bergerak ke timur 3 unit ke (3, 4).
  4. Titik terjauh yang pernah diperoleh robot dari asal ialah (3, 4), yang kuasa dua ialah 32 + 42 = 25 unit jauhnya.

Contoh 2:

• Input: arahan = [4,-1,4,-2,4], halangan = [[2,4]]
• Output: 65
• Penjelasan: Robot bermula pada (0, 0):
  1. Bergerak ke utara 4 unit ke (0, 4).
  2. Belok kanan.
  3. Bergerak ke timur 1 unit dan disekat oleh halangan di (2, 4), robot berada di (1, 4).
  4. Belok kiri.
  5. Bergerak ke utara 4 unit ke (1, 8).
  6. Titik terjauh yang pernah robot perolehi dari asal ialah (1, 8), yang kuasa dua ialah 12 + 82 = 65 unit jauhnya.

Contoh 3:

• Input: arahan = [6,-1,-1,6], halangan = []
• Output: 36
• Penjelasan: Robot bermula pada (0, 0):
  1. Bergerak ke utara 6 unit ke (0, 6).
  2. Belok kanan.
  3. Belok kanan.
  4. Bergerak ke selatan 6 unit ke (0, 0).
  5. Titik paling jauh yang pernah diperoleh robot dari asal ialah (0, 6), yang kuasa dua ialah 62 = 36 unit jauhnya.

Kekangan:

• 1 <= commands.length <= 10⁴
• perintah[i] sama ada -2, -1 atau integer dalam julat [1, 9].
• 0 <= halangan.panjang <= 10⁴
• -3 * 10⁴ <= x_i, y_i <= 3 * 10⁴
• Jawapan dijamin kurang daripada 2³¹

Penyelesaian:

Kita perlu mensimulasikan pergerakan robot pada grid 2D tanpa had berdasarkan urutan arahan dan mengelakkan halangan jika ada. Matlamatnya adalah untuk menentukan jarak Euclidean maksimum kuasa dua yang dicapai oleh robot dari asal.

Pendekatan

1. Pengendalian Arah:

   • Robot boleh menghadap satu daripada empat arah: Utara, Timur, Selatan dan Barat.
   • Kami boleh mewakili arah ini sebagai vektor:
     • Utara: (0, 1)
     • Timur: (1, 0)
     • Selatan: (0, -1)
     • Barat: (-1, 0)

2. Berpusing:

   • Pusingan kiri (-2) akan menganjak arah lawan jam sebanyak 90 darjah.
   • Pusingan kanan (-1) akan beralih arah mengikut arah jam sebanyak 90 darjah.

3. Pergerakan:

   • Untuk setiap arahan pergerakan, robot akan bergerak mengikut arah semasanya, satu unit pada satu masa. Jika ia menghadapi halangan, ia berhenti bergerak untuk arahan itu.

4. Menjejaki Halangan:

   • Tukar senarai halangan kepada satu set tupel untuk carian pantas, membolehkan robot menentukan dengan cepat sama ada ia akan melanggar halangan.

5. Pengiraan Jarak:

   • Jejak jarak maksimum kuasa dua dari asal yang dicapai robot semasa pergerakannya.

Mari laksanakan penyelesaian ini dalam PHP: 874. Simulasi Robot Berjalan

  
  
  Penjelasan:




Pengurusan Arah: Kami menggunakan senarai vektor untuk mewakili arah, membolehkan pengiraan mudah kedudukan seterusnya selepas bergerak.

Pengesanan Halangan: Dengan menyimpan halangan dalam set, kami mencapai kerumitan masa O(1) untuk menyemak sama ada kedudukan disekat oleh halangan.

Pengiraan Jarak: Kami sentiasa mengemas kini jarak kuasa dua maksimum yang dicapai robot semasa ia bergerak.



  
  
  Kes Ujian



Contoh kes ujian yang disediakan digunakan untuk mengesahkan penyelesaian:



[4,-1,3] tanpa halangan harus kembali 25.

[4,-1,4,-2,4] dengan halangan [[2,4]] sepatutnya kembali 65.

[6,-1,-1,6] tanpa halangan harus kembali 36.







Penyelesaian ini cekap mengendalikan kekangan masalah dan mengira jarak maksimum kuasa dua seperti yang diperlukan.

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