Check if a path sequence visits any coordinate two or more times

In some applications we may be interested in checking whether a path sequence visits any coordinate twice. This is useful in GPS tracking systems, for example, to detect if a vehicle is moving back and forth between two points. In this article, we will discuss how to check whether a path sequence visits any coordinate twice, and its implementation in C.

algorithm

To solve this problem, we can use a hash table to keep track of all coordinates visited so far. We first access the first coordinate in the sequence and add it to the hash table. Then, for each subsequent coordinate in the sequence, we check if it is already in the hash table. If it is, we know we've accessed this coordinate before and we can return true. If not, we add it to the hash table and move on to the next coordinate. If we visited all coordinates without finding any duplicates, we can return false.

Example

This is the implementation of the above algorithm in 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;
}

Output

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

Test case example

Consider the sequence "UDDLLRUUUDU" representing the path "up, down, down, left, left, right, up, up, down, up".

We start from the origin (0, 0) and traverse the path, updating coordinates along the way.

At each step, we check whether the new coordinates have been visited before. If so, we know that the sequence visited a coordinate twice and we return true. If not, we mark the coordinate as visited and continue.

Here's how the algorithm works for a given sequence -

• Start from the origin (0, 0)

• “U” − Move up to (0, 1). Mark (0, 1) as visited.

• "D" − Move down to (0, 0). Mark (0, 0) as visited.

• "D"− Move down to (0, -1). Mark (0, -1) as visited.

• “L” − Move left to (-1, -1). Mark (-1, -1) as visited.

• “L” − Move left to (-2, -1). Mark (-2, -1) as visited.

• “R” − Move right to (-1, -1). This coordinate has been visited before, so we return true.

Since the sequence accesses the coordinates twice, the function returns true.

So, for the given sequence "UDDLLRUUUDU", the function correctly returns the sequence accessed coordinates twice.

in conclusion

In this article, we discussed how to check if a path sequence visits any coordinate twice. We use a hash table to keep track of all coordinates visited so far and check for duplicates at each step. We also provide a C implementation of the algorithm

The above is the detailed content of Check if a path sequence visits any coordinate two or more times. For more information, please follow other related articles on the PHP Chinese website!