. Simulation de robot marcheur

874. Simulation de robot marchant

Difficulté :Moyen

Sujets : Tableau, table de hachage, simulation

Un robot sur un plan XY infini commence au point (0, 0) face au nord. Le robot peut recevoir une séquence de ces trois types de commandes possibles :

• -2 : Tourner à gauche à 90 degrés.
• -1 : Tourner à droite à 90 degrés.
• 1 <= k <= 9 : Avancez de k unités, une unité à la fois.

Certaines cases de la grille sont des obstacles. Le ième obstacle est au point de grille obstacles[i] = (x_i, y_i). Si le robot rencontre un obstacle, il restera à son emplacement actuel et passera à la commande suivante.

Renvoyer _la distance euclidienne maximale que le robot obtient jamais depuis l'origine au carré (c'est-à-dire si la distance est de 5, renvoyer 25).

Remarque :

• Le Nord signifie la direction +Y.
• Est signifie direction +X.
• Sud signifie direction -Y.
• Ouest signifie direction -X.
• Il peut y avoir un obstacle dans [0,0].

Exemple 1 :

• Entrée : commandes = [4,-1,3], obstacles = []
• Sortie : 25
• Explication : Le robot démarre à (0, 0) :
  1. Déplacez-vous vers le nord de 4 unités jusqu'à (0, 4).
  2. Tournez à droite.
  3. Déplacez-vous vers l'est de 3 unités jusqu'à (3, 4).
  4. Le point le plus éloigné que le robot ait jamais atteint de l'origine est (3, 4), dont le carré est de 32 + 42 = 25 unités.

Exemple 2 :

• Entrée : commandes = [4,-1,4,-2,4], obstacles = [[2,4]]
• Sortie : 65
• Explication : Le robot démarre à (0, 0) :
  1. Déplacez-vous vers le nord de 4 unités jusqu'à (0, 4).
  2. Tournez à droite.
  3. Déplacez-vous vers l'est d'1 unité et soyez bloqué par l'obstacle en (2, 4), le robot est en (1, 4).
  4. Tournez à gauche.
  5. Déplacez-vous vers le nord de 4 unités jusqu'à (1, 8).
  6. Le point le plus éloigné que le robot ait jamais atteint de l'origine est (1, 8), dont le carré est 12 + 82 = 65 unités.

Exemple 3 :

• Entrée : commandes = [6,-1,-1,6], obstacles = []
• Sortie : 36
• Explication : Le robot démarre à (0, 0) :
  1. Déplacez-vous vers le nord de 6 unités jusqu'à (0, 6).
  2. Tournez à droite.
  3. Tournez à droite.
  4. Déplacez-vous vers le sud de 6 unités jusqu'à (0, 0).
  5. Le point le plus éloigné que le robot ait jamais atteint de l'origine est (0, 6), ce qui au carré est à 62 = 36 unités.

Contraintes :

• 1 <= commands.length <= 10⁴
• commands[i] est soit -2, -1, soit un entier compris dans la plage [1, 9].
• 0 <= obstacles.length <= 10⁴
• -3 * 10⁴ <= x_i, y_i <= 3 * 10⁴
• La réponse est garantie inférieure à 2³¹

Solution :

Nous devons simuler le mouvement du robot sur une grille 2D infinie basée sur une séquence de commandes et éviter les éventuels obstacles. Le but est de déterminer la distance euclidienne maximale au carré que le robot atteint depuis l'origine.

Approche

1. Gestion des directions :

   • Le robot peut faire face à l'une des quatre directions suivantes : Nord, Est, Sud et Ouest.
   • Nous pouvons représenter ces directions sous forme de vecteurs :
     • Nord : (0, 1)
     • Est : (1, 0)
     • Sud : (0, -1)
     • Ouest : (-1, 0)

2. Tournage :

   • Un virage à gauche (-2) décalera la direction de 90 degrés dans le sens inverse des aiguilles d'une montre.
   • Un virage à droite (-1) décalera la direction dans le sens des aiguilles d'une montre de 90 degrés.

3. Mouvement :

   • Pour chaque commande de déplacement, le robot se déplacera dans sa direction actuelle, une unité à la fois. S'il rencontre un obstacle, il s'arrête de bouger pour cette commande.

4. Suivi des obstacles :

   • Convertissez la liste des obstacles en un ensemble de tuples pour une recherche rapide, permettant au robot de déterminer rapidement s'il heurtera un obstacle.

5. Calcul de la distance :

   • Suivez la distance maximale au carré de l'origine que le robot atteint lors de ses mouvements.

Implémentons cette solution en PHP : 874. Simulation de robot marchant

  
  
  Explication:




Gestion des directions : Nous utilisons une liste de vecteurs pour représenter les directions, permettant un calcul facile de la position suivante après le déplacement.

Détection d'obstacles : En stockant les obstacles dans un ensemble, nous obtenons une complexité temporelle O(1) pour vérifier si une position est bloquée par un obstacle.

Calcul de la distance : Nous mettons continuellement à jour la distance carrée maximale atteinte par le robot lorsqu'il se déplace.



  
  
  Cas de test



Les exemples de cas de tests fournis permettent de valider la solution :



[4,-1,3] sans obstacles devrait renvoyer 25.

[4,-1,4,-2,4] avec des obstacles [[2,4]] devrait renvoyer 65.

[6,-1,-1,6] sans obstacles devrait renvoyer 36.







Cette solution gère efficacement les contraintes du problème et calcule la distance maximale au carré selon les besoins.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!