Vérifiez si une séquence de chemin visite une coordonnée deux fois ou plus

Dans certaines applications, nous pouvons être intéressés à vérifier si une séquence de chemin visite deux fois une coordonnée. Ceci est utile dans les systèmes de suivi GPS, par exemple, pour détecter si un véhicule se déplace entre deux points. Dans cet article, nous verrons comment vérifier si une séquence de chemin visite deux fois une coordonnée et son implémentation en C++.

Algorithme

Pour résoudre ce problème, nous pouvons utiliser une table de hachage pour garder une trace de toutes les coordonnées visitées jusqu'à présent. Nous accédons d’abord à la première coordonnée de la séquence et l’ajoutons à la table de hachage. Ensuite, pour chaque coordonnée suivante de la séquence, nous vérifions si elle est déjà dans la table de hachage. Si tel est le cas, nous savons que nous avons déjà accédé à ces coordonnées et nous pouvons renvoyer true. Sinon, nous l'ajoutons à la table de hachage et passons à la coordonnée suivante. Si nous avons visité toutes les coordonnées sans trouver de doublons, nous pouvons renvoyer false.

Exemple

Il s'agit de l'implémentation de l'algorithme ci-dessus en C++−

#include<bits/stdc++.h>
using namespace std;

bool isVisitedTwice(int n, int path[][2]) {
   set<pair<int, int>> visited;
   for(int i=0;i<n;i++) {
      // Check if the current coordinate has already been visited
      if(visited.find(make_pair(path[i][0], path[i][1])) != visited.end()) {
         return true;
      }
      visited.insert(make_pair(path[i][0], path[i][1]));
   }
   return false;
}

int main() {

   // Test case 1
   int path1[5][2] = {{0,0},{1,1},{2,2},{3,3},{4,4}};
   if(isVisitedTwice(5, path1)) {
      cout << "Sequence visits a coordinate twice" << endl;
   } else {
      cout << "Sequence does not visit a coordinate twice" << endl;
   }
   
   // Test case 2
   int path2[6][2] = {{0,0},{1,1},{2,2},{3,3},{4,4},{3,3}};
   if(isVisitedTwice(6, path2)) {
      cout << "Sequence visits a coordinate twice" << endl;
   } else {
      cout << "Sequence does not visit a coordinate twice" << endl;
   }
   
   // Test case 3
   int path3[3][2] = {{0,0},{1,1},{2,2}};
   if(isVisitedTwice(3, path3)) {
      cout << "Sequence visits a coordinate twice" << endl;
   } else {
      cout << "Sequence does not visit a coordinate twice" << endl;
   }

   return 0;
}

Sortie

Sequence does not visit a coordinate twice
Sequence visits a coordinate twice
Sequence does not visit a coordinate twice

Exemple de cas de test

Considérons la séquence "UDDLLRUUUDU" représentant le chemin "haut, bas, bas, gauche, gauche, droite, haut, haut, bas, haut".

Nous partons de l'origine (0, 0) et parcourons le chemin, en mettant à jour les coordonnées en cours de route.

A chaque étape nous vérifions si les nouvelles coordonnées ont déjà été visitées. Si tel est le cas, nous savons que la séquence a visité une coordonnée deux fois et nous renvoyons vrai. Sinon, nous marquons les coordonnées comme visitées et continuons.

Voici comment fonctionne l'algorithme pour une séquence donnée -

• Partir de l'origine (0, 0)

• « U » − Se déplace jusqu'à (0, 1). Marquez (0, 1) comme visité.

• «D» − Descend jusqu'à (0, 0). Marquez (0, 0) comme visité.

• « D »− descend à (0, -1). Marquez (0, -1) comme visité.

• « L » − Déplacez-vous vers la gauche jusqu'à (-1, -1). Marquez (-1, -1) comme visité.

• « L » − Déplacez-vous vers la gauche jusqu'à (-2, -1). Marquez (-2, -1) comme visité.

• “R” − Déplacez-vous vers la droite jusqu'à (-1, -1). Cette coordonnée a déjà été visitée, nous retournons donc vrai.

Puisque la séquence accède aux coordonnées deux fois, la fonction renvoie vrai.

Ainsi, pour la séquence donnée "UDDLLRUUUDU", la fonction renvoie correctement les coordonnées de la séquence accédées deux fois.

Conclusion

Dans cet article, nous avons expliqué comment vérifier si une séquence de chemin visite deux fois une coordonnée. Nous utilisons une table de hachage pour garder une trace de toutes les coordonnées visitées jusqu'à présent et vérifier les doublons à chaque étape. Nous fournissons également une implémentation C de l'algorithme

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!