檢查一個路徑序列是否訪問了任何坐標兩次或更多次

在某些應用程式中，我們可能有興趣檢查路徑序列是否存取任何座標兩次。例如，這在 GPS 追蹤系統中非常有用，可以偵測車輛是否在兩點之間來回移動。在本文中，我們將討論如何檢查路徑序列是否存取任意座標兩次，及其在 C 中的實作。

演算法

為了解決這個問題，我們可以使用雜湊表來追蹤迄今為止所訪問過的所有座標。我們首先訪問序列中的第一個座標，並將其添加到哈希表中。然後，對於序列中的每個後續座標，我們檢查它是否已經在雜湊表中。如果是，我們就知道我們之前訪問過這個座標，我們可以回傳 true。如果不是，我們將其添加到哈希表中並繼續下一個座標。如果我們訪問了所有座標而沒有找到任何重複項，我們可以傳回 false。

範例

這是上述演算法在 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;
}

輸出

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

測試案例範例

考慮代表路徑「上、下、下、左、左、右、上、上、下、上」的序列「UDDLLRUUUDU」。

我們從原點 (0, 0) 開始，遍歷路徑，沿途更新座標。

在每一步中，我們都會檢查之前是否已經訪​​問過新座標。如果是，我們知道該序列訪問了一個坐標兩次，我們返回 true。如果沒有，我們將座標標記為已訪問並繼續。

以下是演算法如何針對給定序列工作的 -

• 從原點 (0, 0) 開始

• #「U」 − 向上移動到 (0, 1)。將 (0, 1) 標記為已訪問。

• #「D」 − 向下移動到 (0, 0)。將 (0, 0) 標記為已存取。

• #「D」− 向下移動到 (0, -1)。將 (0, -1) 標記為已訪問。

• #「L」 − 向左移到 (-1, -1)。將 (-1, -1) 標記為已訪問。

• #「L」 − 向左移到 (-2, -1)。將 (-2, -1) 標記為已訪問。

• #「R」 − 右邊移至 (-1, -1)。這個座標之前已經被訪問過，所以我們回傳true。

#由於序列訪問座標兩次，因此函數傳回 true。

因此，對於給定的序列“UDDLLRUUUDU”，該函數正確地傳回該序列存取座標兩次。

結論

在本文中，我們討論如何檢查路徑序列是否訪問任何座標兩次。我們使用哈希表來追蹤迄今為止訪問過的所有座標，並在每一步中檢查重複項。我們也提供了該演算法的 C 實作

以上是檢查一個路徑序列是否訪問了任何坐標兩次或更多次的詳細內容。更多資訊請關注PHP中文網其他相關文章！