Số điểm dừng tối thiểu từ đường dẫn nhất định trong C ++

Tuyên bố vấn đề

• Có nhiều điểm trong không gian hai chiều cần được thăm quan theo một trình tự cụ thể.
• Đường dẫn từ điểm này đến điểm khác luôn được chọn làm đường đi ngắn nhất và các đoạn đường dẫn luôn được căn chỉnh với đường lưới.
• Chúng tôi được cung cấp con đường được chọn để tham quan các điểm. Chúng tôi cần cho biết số điểm tối thiểu cần thiết để tạo các đường dẫn nhất định.

Thuật toán

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

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum stops = 3