इस समस्या में, हमें n पूर्णांकों का एक चक्रव्यूह दिया जाता है, प्रत्येक पूर्णांक किए जाने वाले चालों की संख्या को इंगित करता है। दिशा के साथ-साथ '>' और '<' का प्रयोग करते हुए दर्शाया गया है। हमारा काम यह पता लगाना है कि क्या भूलभुलैया से बाहर निकलना संभव है या नहीं, अगर शुरुआती बिंदु 0 इंडेक्स पर स्थित है।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट -
3 2 1 1 4 > < > >
आउटपुट - हाँ
स्पष्टीकरण - शुरुआत से आगे बढ़ते हुए, हम 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 << "It stays inside the maze forever";
else
cout << "It will come out of the maze";
}
int main (){
int n = 3;
string s = ">><";
int a[] = { 1, 2, 4 };
isMazeSolvable (a, n, s);
} आउटपुट
It will come out of the maze