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