एक भूलभुलैया समस्या में चूहा

इस समस्या में, N x N आकार की एक दी गई भूलभुलैया है। स्रोत और गंतव्य स्थान क्रमशः शीर्ष-बाएं कक्ष और निचला दायां कक्ष है। कुछ सेल चलने के लिए मान्य होते हैं और कुछ सेल ब्लॉक हो जाते हैं। यदि एक चूहा प्रारंभ शीर्ष से गंतव्य शीर्ष की ओर बढ़ना शुरू करता है, तो हमें यह पता लगाना होगा कि क्या पथ को पूरा करने का कोई तरीका है, यदि संभव हो तो चूहे के लिए सही पथ चिह्नित करें।

भूलभुलैया एक बाइनरी मैट्रिक्स का उपयोग करके दी गई है, जहां इसे 1 के साथ चिह्नित किया गया है, यह एक वैध पथ है, अन्यथा अवरुद्ध सेल के लिए 0 है।

नोट: चूहा केवल दो दिशाओं में चल सकता है, या तो दाईं ओर या नीचे की ओर।

इनपुट और आउटपुट

इनपुट:यह एल्गोरिथम भूलभुलैया को एक मैट्रिक्स के रूप में लेगा। मैट्रिक्स में, मान 1 मुक्त स्थान को इंगित करता है और 0 दीवार या अवरुद्ध क्षेत्र को इंगित करता है। इस आरेख में, ऊपर-बाएं वृत्त प्रारंभिक बिंदु को इंगित करता है और निचला-दायां वृत्त अंतिम बिंदु को इंगित करता है .आउटपुट:यह एक मैट्रिक्स प्रदर्शित करेगा। उस मैट्रिक्स से, हम गंतव्य बिंदु तक पहुंचने के लिए चूहे का मार्ग ढूंढ सकते हैं। 

एल्गोरिदम

वैध है(x, y)

इनपुट: भूलभुलैया में x और y बिंदु।

आउटपुट: सही है अगर (x,y) स्थान मान्य है, अन्यथा गलत है।

शुरू करें यदि x और y सीमा में हैं और (x,y) स्थान अवरुद्ध नहीं है, तो सही रिटर्न falseEnd वापस करें

हल करेंRatMaze(x, y)

इनपुट - शुरुआती बिंदु x और y।

आउटपुट - मंज़िल तक पहुँचने के लिए चूहे के पीछे चलने का रास्ता, नहीं तो गलत।

शुरू करें अगर (x,y) निचला दायां कोना है, तो जगह को 1 रिटर्न ट्रू के रूप में चिह्नित करें यदि isValidPlace(x, y) =true है, तो (x, y) जगह को 1 के रूप में चिह्नित करें यदि हल करेंRatMaze(x+1 , y) =सच, फिर // फॉरवर्ड मूवमेंट के लिए रिटर्न ट्रू अगर सॉल्व रैटमैज़ (x, y+1) =ट्रू, तो // डाउन मूवमेंट के लिए ट्रू मार्क (x, y) को 0 के रूप में लौटाएं जब बैकट्रैक्स झूठी रिटर्न झूठी वापसी करें। पूर्व> 
उदाहरण
 
#शामिल करें#define N 5नेमस्पेस का उपयोग कर std;int maze[N][N] ={ {1, 0, 0, 0, 0}, {1, 1, 0, 1, 0}, { 0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 1}}; इंट सोल [एन] [एन]; // भूलभुलैया पथ का अंतिम समाधान यहां संग्रहीत है शोपाथ() {के लिए (int i =0; i =0 &&x =0 &&y  
आउटपुट
 
1 0 0 0 01 1 0 0 00 1 1 1 00 0 0 1 00 0 0 1 1