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