. Laufrobotersimulation

874. Laufrobotersimulation

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Simulation

Ein Roboter auf einer unendlichen XY-Ebene startet am Punkt (0, 0) in Richtung Norden. Der Roboter kann eine Folge dieser drei möglichen Befehlstypen empfangen:

• -2: 90 Grad nach links drehen.
• -1: 90 Grad nach rechts drehen.
• 1 <= k <= 9: K Einheiten vorwärts bewegen, eine Einheit nach der anderen.

Einige der Planquadrate sind Hindernisse. Das i-te Hindernis befindet sich am Gitterpunkt hindernisse[i] = (x_i, y_i). Wenn der Roboter auf ein Hindernis stößt, bleibt er stattdessen an seinem aktuellen Standort und geht zum nächsten Befehl über.

Gib _den maximalen euklidischen Abstand zurück, den der Roboter jemals vom Ursprung im Quadrat erreicht (d. h. wenn der Abstand 5 beträgt, geben Sie 25 zurück).

Hinweis:

• Norden bedeutet +Y-Richtung.
• Osten bedeutet +X-Richtung.
• Süd bedeutet -Y-Richtung.
• Westen bedeutet -X-Richtung.
• Es kann ein Hindernis in [0,0] geben.

Beispiel 1:

• Eingabe: Befehle = [4,-1,3], Hindernisse = []
• Ausgabe: 25
• Erklärung: Der Roboter startet bei (0, 0):
  1. Bewege dich 4 Einheiten nach Norden zu (0, 4).
  2. Biegen Sie rechts ab.
  3. Bewege dich 3 Einheiten nach Osten zu (3, 4).
  4. Der am weitesten vom Ursprung entfernte Punkt, den der Roboter jemals erreicht, ist (3, 4), was im Quadrat 32 + 42 = 25 Einheiten beträgt.

Beispiel 2:

• Eingabe: Befehle = [4,-1,4,-2,4], Hindernisse = [[2,4]]
• Ausgabe: 65
• Erklärung: Der Roboter startet bei (0, 0):
  1. Bewege dich 4 Einheiten nach Norden zu (0, 4).
  2. Biegen Sie rechts ab.
  3. Bewege dich 1 Einheit nach Osten und werde vom Hindernis bei (2, 4) blockiert, der Roboter ist bei (1, 4).
  4. Biegen Sie links ab.
  5. Bewege dich 4 Einheiten nach Norden zu (1, 8).
  6. Der am weitesten vom Ursprung entfernte Punkt, den der Roboter jemals erreicht, ist (1, 8), was im Quadrat 12 + 82 = 65 Einheiten beträgt.

Beispiel 3:

• Eingabe: Befehle = [6,-1,-1,6], Hindernisse = []
• Ausgabe: 36
• Erklärung: Der Roboter startet bei (0, 0):
  1. Bewege dich 6 Einheiten nach Norden zu (0, 6).
  2. Biegen Sie rechts ab.
  3. Biegen Sie rechts ab.
  4. Bewege dich 6 Einheiten nach Süden auf (0, 0).
  5. Der am weitesten vom Ursprung entfernte Punkt, den der Roboter jemals erreicht, ist (0, 6), was im Quadrat 62 = 36 Einheiten beträgt.

Einschränkungen:

• 1 <= commands.length <= 10⁴
• commands[i] ist entweder -2, -1 oder eine Ganzzahl im Bereich [1, 9].
• 0 <= Hindernisse.Länge <= 10⁴
• -3 * 10⁴ <= x_i, y_i <= 3 * 10⁴
• Die Antwort liegt garantiert unter 2³¹

Lösung:

Wir müssen die Bewegung des Roboters auf einem unendlichen 2D-Gitter basierend auf einer Abfolge von Befehlen simulieren und etwaigen Hindernissen ausweichen. Das Ziel besteht darin, den maximalen euklidischen Abstand im Quadrat zu bestimmen, den der Roboter vom Ursprung aus erreicht.

Ansatz

1. Richtungshandhabung:

   • Der Roboter kann in eine von vier Richtungen blicken: Norden, Osten, Süden und Westen.
   • Wir können diese Richtungen als Vektoren darstellen:
     • Norden: (0, 1)
     • Osten: (1, 0)
     • Süden: (0, -1)
     • Westen: (-1, 0)

2. Drehen:

   • Eine Linkskurve (-2) verschiebt die Richtung um 90 Grad gegen den Uhrzeigersinn.
   • Eine Rechtsdrehung (-1) verschiebt die Richtung im Uhrzeigersinn um 90 Grad.

3. Bewegung:

   • Bei jedem Bewegungsbefehl bewegt sich der Roboter jeweils eine Einheit in seine aktuelle Richtung. Wenn es auf ein Hindernis trifft, stoppt es aufgrund dieses Befehls.

4. Hindernisse verfolgen:

   • Konvertieren Sie die Hindernisliste in eine Reihe von Tupeln für eine schnelle Suche, damit der Roboter schnell feststellen kann, ob er auf ein Hindernis stößt.

5. Entfernungsberechnung:

   • Verfolgen Sie den maximalen Abstand im Quadrat vom Ursprung, den der Roboter während seiner Bewegungen erreicht.

Lassen Sie uns diese Lösung in PHP implementieren: 874. Laufrobotersimulation

  
  
  Erläuterung:




Richtungsverwaltung: Wir verwenden eine Liste von Vektoren zur Darstellung der Richtungen, was eine einfache Berechnung der nächsten Position nach der Bewegung ermöglicht.

Hinderniserkennung: Durch das Speichern von Hindernissen in einem Satz erreichen wir eine O(1)-Zeitkomplexität für die Überprüfung, ob eine Position durch ein Hindernis blockiert ist.

Entfernungsberechnung: Wir aktualisieren kontinuierlich die maximale quadratische Entfernung, die der Roboter während seiner Bewegung erreicht.



  
  
  Testfälle



Die bereitgestellten Beispieltestfälle werden zur Validierung der Lösung verwendet:



[4,-1,3] ohne Hindernisse sollte 25 zurückgeben.

[4,-1,4,-2,4] mit Hindernissen [[2,4]] sollte 65 zurückgeben.

[6,-1,-1,6] ohne Hindernisse sollte 36 zurückgeben.







Diese Lösung behandelt die Problembeschränkungen effizient und berechnet den maximalen Abstand im Quadrat nach Bedarf.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
        
Das obige ist der detaillierte Inhalt von. Laufrobotersimulation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!