इस समस्या में, हमें n पूर्णांकों की एक भूलभुलैया दी गई है, प्रत्येक पूर्णांक किए जाने वाले चालों की संख्या को इंगित करता है। साथ ही दिशा '>' और '<' का उपयोग करके इंगित की गई है। हमारा कार्य यह पता लगाना है कि क्या भूलभुलैया से बाहर निकलना संभव है या नहीं यदि शुरुआती बिंदु 0 इंडेक्स पर स्थिति है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट -
3 2 1 1 4 > < > >
आउटपुट - YES
व्याख्या - शुरुआत से चलते हुए, हम 2 पोजीशन आगे बढ़ेंगे, फिर 1 पोजीशन आगे, फिर 4 पोजीशन आगे। यह हमें भूलभुलैया से बाहर ले जाएगा।
इस समस्या को हल करने के लिए, हम जांचेंगे कि भूलभुलैया से बाहर निकलना संभव है या नहीं। इसके लिए या तो हमें 0 से नीचे या n से ऊपर जाने की आवश्यकता है। 0 से शुरू करके, हम दिए गए पूर्णांक स्थानों द्वारा चिह्न के आधार पर दिशा को संसाधित करेंगे। और जांचेंगे कि क्या अंत पहुंच गया है।
एक और स्थिति जो उत्पन्न हो सकती है वह है अनंत लूप, यानी वह स्थिति जब उपयोगकर्ता कभी भी भूलभुलैया से बाहर नहीं निकलता, यह तब होता है जब हम एक विज़िट की गई स्थिति पर वापस आते हैं। इसलिए, इस स्थिति की जांच के लिए हम सभी विज़िट किए गए स्थानों को चिह्नित करेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम
#include <iostream>
using namespace std;
void isMazeSolvable(int a[], int n, string s) {
int mark[n] = {0};
int start = 0;
int possible = 1;
while (start >= 0 && start < n) {
if (s == "<") {
if (mark[start] == 0) {
mark[start] = 1;
start -= a[start];
} else {
possible = 0;
break;
}
} else {
if (mark[start] == 0) {
mark[start] = 1;
start += a[start];
} else {
possible = 0;
break;
}
}
}
if (possible == 0)
cout << "यह भूलभुलैया में हमेशा के लिए रहता है";
else
cout << "यह भूलभुलैया से बाहर आ जाएगा";
}
int main() {
int n = 3;
string s = ">><";
int a[] = {1, 2, 4};
isMazeSolvable(a, n, s);
}
आउटपुट
यह भूलभुलैया से बाहर आ जाएगा