在C ++中从给定路径停止的最小次数

问题陈述

• 二维空间中有许多需要按特定顺序访问的点。

• 总是选择从一个点到另一个点的路径，因为最短路径和路径段始终与网格线对齐。

• 我们为选择要点提供了路径。我们需要告知生成给定路径所需的最少点数。

算法

1. We can solve this problem by observing the pattern of movement when visiting the stop
2. If we want to take the shortest path from one point to another point, then we will move in either one or max two directions

示例

#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
   int n = path.length();
   map<char, int> directionMap;
   int stops = 1;
   for (int i = 0; i < n; ++i) {
      char direction = path[i];
      directionMap[direction] = 1;
      if ((directionMap['L'] && directionMap['R']) ||
      (directionMap['U'] && directionMap['D'])) {
         directionMap.clear();
         ++stops;
         directionMap[direction] = 1;
      }
   }
   return stops + 1;
}
int main() {
   string path = "LLUUULLDD";
   cout << "Minimum stops = " << getMinStops(path) << endl;
   return 0;
}

当您编译并执行上述程序时。它产生以下输出

输出结果

Minimum stops = 3