C++で指定されたパスからの最小ストップ数

問題の説明

• 2次元空間には、特定の順序でアクセスする必要のあるポイントが多数あります。
• あるポイントから別のポイントへのパスは常に最短パスとして選択され、パスセグメントは常にグリッド線に揃えられます。
• ポイントを訪問するために選択されたパスが与えられます。特定のパスを生成するために必要な最小ポイント数を指定する必要があります。

アルゴリズム

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