C++ 计算沿着给定字符串指定路径移动时返回的点数

在这个问题中，我们给出了一个字符串，表示移动方向和起始坐标。我们需要找到再次访问的位置。

我们可以使用集合或映射数据结构来存储先前访问的坐标。如果在集合或映射中找到任何一对位置，我们可以说该位置被再次访问。

问题描述 - 我们给出了一个长度为N的字符串str，其中包含’L’、’R’、’U’和’D’字符。此外，我们给出了X和Y整数，表示起始位置。我们需要根据以下条件找到在遵循路径时重复访问的坐标的总数。

• 对于字符’L’，向左移动，将X的值减1。

• 对于字符’R’，向右移动，将X的值增加1。

• 对于字符’U’，向上移动，将Y的值增加1。

• 对于字符’D’，向下移动，将Y的值减1。

示例

输入 - str = “DDRULRD”, X = 0, Y = 0

输出 - 2

解释 - 根据给定的字符串跟踪移动。

(0, -1) -> (0, -2) -> (1, -2) -> (1, -1) -> (0, -1) ->(1, -1) -> (1, 0).

以上路径显示(0, -1)和(1, -1)被重新访问了。

输入 - str = “RLUDRDDUU”, X = 3, Y = 5

输出 - 5

解释 - 路径移动如下所示。

(4, 5) -> (3, 5) -> (3, 6) -> (3, 5) ->(4, 5) -> (4, 4) -> (4, 3) -> (4, 4) -> (4, 5).

在上述位置中，(4, 5)重复两次，(3,5)重复两次，因为初始位置相同，(4, 4)重复一次。

方法1

在这个方法中，我们将使用集合数据结构来跟踪移动。我们将根据当前字符将+1或-1添加到X或Y坐标中。在更新位置后，如果我们发现位置坐标已经存在于集合中，我们可以说它被重新访问了。

步骤

• 使用字符串的长度来初始化变量’len’。

• 使用零来初始化变量’x_pos’和’y_pos’。定义变量’cnt’来存储重新访问位置的数量。

• 定义集合，并使用insert()方法将初始坐标对插入。

• 开始遍历字符串。在循环中，使用if-else语句根据当前字符来更新位置。

  • 如果当前字符是’U’，则设置y_pos = 1和x_pos = 0。如果字符是’D’，则设置y_pos = -1和x_pos = 0；

  • 如果当前字符是’R’，则设置y_pos = 0和x_pos = 1。如果字符是’L’，则设置y_pos = 0和x_pos = -1；

• 将x_pos添加到X，将y_pos添加到Y。

• 使用find()方法检查集合中是否存在X和Y。如果存在，则将’cnt’的值增加1。否则，将该坐标对插入集合。

• 返回’cnt’的值。

示例

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

// function to cnt the total number of revisited positions
int countRevisited(string str, int X, int Y) {
   // Stores the length of the string
   int len = str.length();
   // to store the current position
   int x_pos = 0, y_pos = 0;
   // to store the count of revisited positions
   int cnt = 0;
   // Define a set to store the pairs of visited positions
   set<pair<int, int>> pairs;
   // Insert the starting coordinates
   pairs.insert({X, Y});
   // Traverse over the string
   for (int i = 0; i < len; i++) {
      // Modify the current position according to the given direction.
      if (str[i] == 'U') {
          y_pos = 1;
          x_pos = 0;
      } else if (str[i] == 'D') {
         y_pos = -1;
         x_pos = 0;
      } else if (str[i] == 'R') {
          x_pos = 1;
          y_pos = 0;
      } else {
          x_pos = -1;
          y_pos = 0;
      }
      X += x_pos;
      Y += y_pos;
      // If the current position is already visited, then increment cnt by 1
      if (pairs.find({X , Y }) != pairs.end()) {
          cnt++;
      }
      // else insert the current position in the set
      else {
          pairs.insert({X , Y });
      }
   }
   return cnt;
}
int main(){
   string str = "RLUDRDDUU";
   int X = 3, Y = 5;
   cout << "The numbers of revisited coordinates while following the given path are - " << countRevisited(str, X, Y);
   return 0;
}

输出

The numbers of revisited coordinates while following the given path are - 5

时间复杂度 – O(N * logN)，因为我们遍历字符串并在集合中搜索一对。

空间复杂度 – O(N)，因为我们需要在最坏的情况下存储N对。

方法2

这种方法将使用映射数据结构存储访问过的对。此外，我们将在C++中使用switch case语句根据字符串的字符更新当前位置。

步骤

• 定义’len’，’x_pos’，’y_pos’和’cnt’变量。

• 定义映射名称’pairs’并向映射中添加一个初始位置。

• 开始遍历字符串。使用switch()语句根据第i个索引处的字符更新x_pos和y_pos变量的值。

• 将x_pos的值添加到X，将y_pos的值添加到Y。

• 从映射中访问{X，Y}对的值。如果大于0，则表示位置被重新访问，并将’cnt’的值增加1。否则，在映射中为当前对设置值为1。

示例

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

// function to cnt the total number of revisited positions
int countRevisited(string str, int X, int Y) {
   // Stores the length of the string
   int len = str.length();
   // to store the current position
   int x_pos = 0, y_pos = 0;
   // to store the count of revisited positions
   int cnt = 0;
   // Define a map to store the pairs of visited positions
   map<pair<int, int>, int> pairs;
   // Insert the starting coordinates
   pairs[{X, Y}] = 1;
   // Traverse over the string
   for (int i = 0; i < len; i++) {
      // Modify the current position, according to the given direction using the switch statement
      switch (str[i]){
      case 'U':
          y_pos = 1;
          x_pos = 0;
          break;
      case 'D':
          y_pos = -1;
          x_pos = 0;
          break;
      case 'L':
          y_pos = 0;
          x_pos = -1;
          break;
      case 'R':
          y_pos = 0;
          x_pos = 1;
          break;
      }
      X += x_pos;
      Y += y_pos;
      // If the current position is already visited, then increment cnt by 1
      if (pairs[{X, Y}] > 0) {
          cnt++;
      }
      // else insert the current position in the set
      else {
          pairs[{ X, Y}] = 1;
      }
   }
   return cnt;
}
int main(){
   string str = "RLUDRDDUU";
   int X = 3, Y = 5;
   cout << "The numbers of revisited coordinates while following the given path are - " << countRevisited(str, X, Y);
   return 0;
}

输出

The numbers of revisited coordinates while following the given path are - 5

时间复杂度 – O(N*logN)，因为我们遍历字符串并在映射中搜索成对项。

空间复杂度 – O(N)，因为我们使用了映射。