एल्गोरिथ्म एक पाठ के माध्यम से स्क्रीन पथ (ओं) को मुद्रित करने के लिए भूलभुलैया

Question

मेरी सी ++ काम के लिए, मैं मूल रूप से (है कि मेरे वेक्टर vec स्ट्रीम है) में शुरुआत एक पाठ फ़ाइल में पाठ का एक हिस्सा के माध्यम से खोज करने के लिए कोशिश कर रहा हूँ बाईं ओर दूसरा शीर्ष चरित्र। यह एक पाठ भूलभुलैया के लिए है, जहां अंत में मेरा कार्यक्रम पात्रों को इसके माध्यम से पथ के लिए मुद्रित करना है।

एक उलझन का एक उदाहरण होगा जैसे:

############### 
Sbcde####efebyj 
####hijk#m##### 
#######lmi##### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 

कहाँ '#' एक unwalkable दीवार है और आप हमेशा दूसरे शीर्ष चरित्र पर छोड़ दिया पर शुरू करते हैं। वर्णमाला वर्ण चलने योग्य वर्गों का प्रतिनिधित्व करते हैं। बाहर निकलें हमेशा दाईं ओर हैं। भूलभुलैया हमेशा एक maze.text फ़ाइल में 15x15 आकार है। वर्णमाला वर्ण एक ही भूलभुलैया के भीतर दोहराते हैं, लेकिन सीधे एक दूसरे के बगल में नहीं।

मैं यहां क्या करने की कोशिश कर रहा हूं: यदि वर्तमान के बगल में एक वर्ग में वर्णमाला वर्ण है, तो इसे वेक्टर vec पर जोड़ें, और जब तक मैं भूलभुलैया के अंत तक नहीं पहुंच जाता तब तक इस प्रक्रिया को दोहराएं। आखिरकार मुझे कुछ मैज में मौजूद स्क्रीन के कई पथों को प्रिंट करके इसे और अधिक जटिल बनाना है।

अब तक मैं एल्गोरिथ्म ही है, जो मुझे पता है के लिए यह राशि गलत है:

void pathcheck() 
{ 
    if (isalpha(vec.at(x)) && !(find(visited.begin(), visited.end(), (vec.at(x))) != visited.end())) 
    { 
     path.push_back(vec.at(x)); 
     visited.push_back(vec.at(x)); 
     pathcheck(vec.at(x++)); 
     pathcheck(vec.at(x--)); 
     pathcheck(vec.at(x + 16)); 
     pathcheck(vec.at(x - 16)); 
    } 
} 

visited दौरा वर्गों की मेरी ट्रैक वेक्टर रखते हुए है।

मैं इसे कैसे अपडेट करूं ताकि यह वास्तव में काम करता है, और अंततः मैं एक से अधिक पथ प्रबंधित कर सकता हूं (यानी यदि 2 पथ थे, तो प्रोग्राम दोनों स्क्रीन पर प्रिंट करेगा)? मुझे याद किया जा रहा है कि मुझे एक और वेक्टर/सरणी की आवश्यकता हो सकती है जो उन वर्गों का ट्रैक रखती है जिन्हें मैंने पहले से देखा/चेक किया है, लेकिन फिर मैं इसे यहां कैसे लागू करूं?

Answer 1

आप सही रास्ते पर हैं। जब मैज़ की बात आती है, तो हल करने की सामान्य विधि या तो गहराई से पहली खोज (कुछ पथ खोजने के लिए सबसे कुशल समाधान) या चौड़ाई-पहली खोज (कम कुशल, लेकिन इष्टतम पथ खोजने के लिए गारेन किया जाता है) के माध्यम से होती है। चूंकि आप एक संपूर्ण खोज करना चाहते हैं, इसलिए ये विकल्प मूल रूप से अदला-बदले में हैं। मेरा सुझाव है कि आप उन पर पढ़ा:

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

मूल रूप से, आप अपने भूलभुलैया पार्स और एक ग्राफ (जहां प्रत्येक गैर "#" एक नोड और प्रत्येक कड़ी है के रूप में यह प्रतिनिधित्व करने की आवश्यकता होगी एक चलने योग्य रास्ता है)। फिर, आप आंशिक पथों की एक सूची रखते हैं (यानी नोड्स की एक सूची, जिस क्रम में आप गए थे, उदाहरण के लिए, [एस, बी, सी] एस से शुरू होने वाला आंशिक पथ है और सी पर समाप्त होता है)। डीएफएस और बीएफएस का मुख्य विचार यह है कि आपके पास आंशिक पथ की एक सूची है, और एक-एक करके आप सूची से वस्तुओं को हटाते हैं, उस आंशिक पथ से आने वाले सभी संभावित आंशिक पथ उत्पन्न करते हैं, फिर उन्हें सूची में रखें और दोहराएं। डीएफएस और बीएफएस के बीच मुख्य अंतर यह है कि डीएफएस इस सूची को ढेर के रूप में लागू करता है (यानी नए आइटमों की सबसे बड़ी प्राथमिकता है) और बीएफएस एक कतार का उपयोग करता है (यानी नए आइटमों की सबसे कम प्राथमिकता है)।

तो, अपने भूलभुलैया डीएफएस उपयोग करने के लिए इसे इस तरह काम करेगा:

1. प्रारंभिक नोड एस है, इसलिए अपने प्रारंभिक पथ बस है [एस]। पुश [एस] अपने ढेर में ([[एस]])।
2. पहले आइटम को पॉप करें (इस मामले में, [एस])।
3. सभी संभावित नोड्स की एक सूची बनाएं जो आप वर्तमान नोड से 1 कदम में पहुंच सकते हैं (आपके मामले में, बस बी)।
4. चरण 3 से प्रत्येक नोड के लिए, अपने वर्तमान आंशिक पथ का हिस्सा हैं जो किसी नोड को हटा दें। यह लूप को रोक देगा। (यानी आंशिक पथ [एस, बी] के लिए, बी से हम सी और एस तक यात्रा कर सकते हैं, लेकिन एस पहले से ही हमारे आंशिक पथ का हिस्सा है इसलिए वापसी करना व्यर्थ है)
5. यदि चरण 4 से नोड्स में से एक लक्ष्य है नोड, एक पूर्ण पथ बनाने के लिए इसे अपने आंशिक पथ में जोड़ें। पथ मुद्रित करें।
6. चरण 4 से प्रत्येक नोड के लिए जो लक्ष्य नोड नहीं है, एक नया आंशिक पथ उत्पन्न करें और इसे स्टैक में दबाएं (यानी [एस] के लिए, हम [एस, बी] उत्पन्न करते हैं और इसे ढेर में दबाते हैं, जो अब [[एस, बी]] की तरह दिखना चाहिए)
7. स्टैक खाली होने तक चरण 2 से 6 को दोहराएं, जिसका अर्थ है कि आपने प्रारंभिक नोड से हर संभव पथ को पार किया है।

नोट: आपके उदाहरण में डुप्लिकेट अक्षर हैं (उदाहरण के लिए, तीन "ई" एस)। आपके मामले के लिए, शायद एक साधारण "नोड" कक्षा बनाएं जिसमें अक्षर धारण करने के लिए एक चर शामिल है। इस तरह प्रत्येक "ई" का अपना उदाहरण होगा और पॉइंटर्स अलग-अलग मान होंगे जो आपको आसानी से अलग बताएंगे। मैं सी ++ ठीक से पता नहीं है, लेकिन छद्म कोड में:

class Node: 
    method Constructor(label): 
     myLabel = label 
     links = list() 

    method addLink(node): 
     links.add(node) 

आप फ़ाइल के प्रत्येक वर्ण को पढ़ सकते हैं और अगर यह नहीं है "#", उस चरित्र के लिए नोड का एक नया उदाहरण बना सकते हैं और जोड़ सकते हैं सब आसन्न नोड्स।

संपादित करें: मैंने पिछले 3 वर्षों को पाइथन डेवलपर के रूप में बिताया है और मुझे थोड़ा खराब हो गया है। निम्नलिखित कोड को देखो।

s = "foo" 
s == "foo" 

पायथन में, यह दावा सत्य है। "==" पायथन में स्ट्रिंग की सामग्री की तुलना करता है। जावा डेवलपर के रूप में मैं अपने दिनों से क्या भूल गया था कि कई भाषाओं में "==" स्ट्रिंग के पॉइंटर्स की तुलना करता है। यही कारण है कि जावा और सी ++ जैसी कई भाषाओं में दावा झूठा है क्योंकि तार स्मृति के विभिन्न हिस्सों को इंगित करते हैं।

मेरा मुद्दा यह है कि क्योंकि यह दावा सत्य नहीं है, तो आप नोड क्लास बनाने के लिए जा सकते हैं और केवल वर्णों की तुलना कर सकते हैं (== का उपयोग करके, strcmp() का उपयोग नहीं कर रहे हैं!) लेकिन यह कोड पढ़ने के लिए थोड़ा उलझन में हो सकता है और दस्तावेज होना चाहिए।

कुल मिलाकर, मैं कुछ प्रकार के नोड क्लास का उपयोग करता हूं क्योंकि यह लागू करने के लिए काफी सरल है और परिणामस्वरूप अधिक पठनीय कोड में परिणाम होता है और केवल एक बार अपनी भूलभुलैया को पार्स करने की आवश्यकता होती है!

अच्छी किस्मत