计算沿给定字符串指定的路径重新访问的点数
在此问题中，我们给出了一个字符串，表示移动方向和起始坐标。我们需要找到重新访问的位置。
我们可以使用集合或映射数据结构来存储之前访问的坐标。如果我们在集合或映射中找到任何一对，我们可以说该位置被重新访问。
问题陈述– 我们给出了一个长度为 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
在此方法中，我们将使用集合数据结构来跟踪移动。我们将根据当前角色向 X 或 Y 坐标添加 +1 或 -1。更新位置后，如果我们发现位置坐标已存在于集合中，我们可以说它已重新访问。
算法
用字符串的长度初始化"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;
// 函数用于计算重新访问位置的总数
int countRevisited(string str, int X, int Y) {
// 存储字符串的长度
int len = str.length();
// 存储当前位置
int x_pos = 0, y_pos = 0;
// 存储重新访问位置的计数
int cnt = 0;
// 定义一个集合来存储访问过的位置对
set<pair<int, int>> pair;
// 插入起始坐标
pair.insert({X, Y});
// 遍历字符串
for (int i = 0; i < len; i++) {
// 根据给定的方向修改当前位置。
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;
// 如果当前位置已经被访问过，则将cnt增加1
if (pairs.find({X , Y }) != pairs.end()) {
cnt++;
}
// 否则，将当前位置插入集合中
else {
pairs.insert({X , Y });
}
}
return cnt;
}
int main(){
string str = "RLUDRDDUU";
int X = 3, Y = 5;
cout << "沿着给定路径重新访问的坐标数量为 - " << countRevisited(str, X, Y);
return 0;
}
输出
沿着给定路径重新访问的坐标数量为 - 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;
// 函数用于计算重新访问位置的总数
int countRevisited(string str, int X, int Y) {
// 存储字符串的长度
int len = str.length();
// 存储当前位置
int x_pos = 0, y_pos = 0;
// 存储重新访问位置的计数
int cnt = 0;
// 定义一个映射来存储访问过的位置对
map<pair<int, int>, int> pair;
// 插入起始坐标
pair[{X, Y}] = 1;
// 遍历字符串
for (int i = 0; i < len; i++) {
// 根据给定的方向使用 switch 语句修改当前位置
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;
// 如果当前位置已经被访问过，则将cnt增加1
if (pairs[{X, Y}] > 0) {
cnt++;
}
// 否则，将当前位置插入集合中
else {
pairs[{ X, Y}] = 1;
}
}
return cnt;
}
int main(){
string str = "RLUDRDDUU";
int X = 3, Y = 5;
cout << "沿着给定路径重新访问的坐标数量为 - " << countRevisited(str, X, Y);
return 0;
}
输出
沿着给定路径重新访问的坐标数量为 - 5
时间复杂度 – O(N*logN)，因为我们迭代字符串并在地图中搜索对。
空间复杂度 – O(N)，因为我们使用地图。
