Semak sama ada urutan laluan melawat mana-mana koordinat dua kali atau lebih

Dalam sesetengah aplikasi, kami mungkin berminat untuk menyemak sama ada jujukan laluan melawat mana-mana koordinat dua kali. Ini berguna dalam sistem penjejakan GPS, contohnya, untuk mengesan sama ada kenderaan bergerak ke sana ke mari antara dua titik. Dalam artikel ini, kita akan membincangkan cara untuk menyemak sama ada urutan laluan melawati mana-mana koordinat dua kali dan pelaksanaannya dalam C++.

Algoritma

Untuk menyelesaikan masalah ini, kita boleh menggunakan jadual cincang untuk menjejaki semua koordinat yang dilawati setakat ini. Kami mula-mula mengakses koordinat pertama dalam jujukan dan menambahnya pada jadual cincang. Kemudian, untuk setiap koordinat seterusnya dalam jujukan, kami menyemak sama ada ia sudah berada dalam jadual cincang. Jika ya, kami tahu kami pernah mengakses koordinat ini sebelum ini dan kami boleh kembali benar. Jika tidak, kami menambahnya pada jadual cincang dan teruskan ke koordinat seterusnya. Jika kami melawati semua koordinat tanpa menemui sebarang pendua, kami boleh mengembalikan palsu.

Contoh

Ini adalah pelaksanaan algoritma di atas dalam 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

Contoh kes ujian

Pertimbangkan urutan "UDDLLRUUUDU" yang mewakili laluan "atas, bawah, bawah, kiri, kiri, kanan, atas, atas, bawah, atas".

Kami bermula dari asal (0, 0) dan melintasi laluan, mengemas kini koordinat di sepanjang jalan.

Pada setiap langkah kami menyemak sama ada koordinat baharu telah dilawati sebelum ini. Jika ya, kami tahu bahawa jujukan itu melawati koordinat dua kali dan kami kembali benar. Jika tidak, kami menandakan koordinat sebagai dilawati dan teruskan.

Begini cara algoritma berfungsi untuk urutan tertentu -

• Mula dari asal (0, 0)

• “U” − Bergerak sehingga (0, 1). Tandakan (0, 1) sebagai dilawati.

• “D” − Bergerak ke bawah ke (0, 0). Tandakan (0, 0) sebagai dilawati.

• “D”− bergerak ke bawah ke (0, -1). Tandakan (0, -1) sebagai dilawati.

• “L” − Bergerak ke kiri ke (-1, -1). Tandakan (-1, -1) sebagai dilawati.

• “L” − Bergerak ke kiri ke (-2, -1). Tandakan (-2, -1) sebagai dilawati.

• “R” − Beralih ke kanan ke (-1, -1). Koordinat ini telah dilawati sebelum ini, jadi kami kembali benar.

Oleh kerana jujukan mengakses koordinat dua kali, fungsi itu kembali benar.

Jadi, untuk jujukan "UDDLLRUUUDU" yang diberikan, fungsi mengembalikan jujukan yang diakses dua kali dengan betul.

Kesimpulan

Dalam artikel ini, kami membincangkan cara menyemak sama ada jujukan laluan melawat mana-mana koordinat dua kali. Kami menggunakan jadual cincang untuk menjejaki semua koordinat yang dilawati setakat ini dan menyemak pendua pada setiap langkah. Kami juga menyediakan pelaksanaan C bagi algoritma

Atas ialah kandungan terperinci Semak sama ada urutan laluan melawat mana-mana koordinat dua kali atau lebih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!