समस्या कथन
- द्वि-आयामी स्थान में कई बिंदु हैं जिन्हें एक विशिष्ट क्रम में देखा जाना है।
- एक बिंदु से दूसरे बिंदु तक का पथ हमेशा सबसे छोटे पथ के रूप में चुना जाता है और पथ खंड हमेशा ग्रिड लाइनों के साथ संरेखित होते हैं।
- हमें वह पथ दिया गया है जिसे बिंदुओं को देखने के लिए चुना गया है। हमें उन न्यूनतम बिंदुओं की संख्या बतानी होगी जो दिए गए पथ उत्पन्न करने के लिए आवश्यक हैं।
एल्गोरिदम
1. हम स्टॉप पर जाने पर गति के पैटर्न को देखकर इस समस्या को हल कर सकते हैं 2. यदि हम एक बिंदु से दूसरे बिंदु तक सबसे छोटा पथ लेना चाहते हैं, तो हम या तो एक या अधिकतम दो दिशाओं में आगे बढ़ेंगे
उदाहरण
#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 << "न्यूनतम स्टॉप = " << getMinStops(path) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
न्यूनतम स्टॉप = 3
