2 डी मानचित्र के पहुंचने योग्य वर्गों को ढूंढना

Question

मैं नहीं चाहता कि आप मेरे लिए इस समस्या को हल करें, मैं बस कुछ विचार पूछना चाहता हूं।

यह नीचे दिया गया इनपुट है, और यह एक मानचित्र का प्रतिनिधित्व करता है। 'एक्स' जमीन का प्रतिनिधित्व करता है, और डॉट्स - पानी। तो 'एक्स' के साथ आप मानचित्र पर 'द्वीप' का प्रतिनिधित्व कर सकते हैं।

xxx.x...xxxxx   
xxxx....x...x   
........x.x.x   
..xxxxx.x...x  
..x...x.xxx.x   
..x.x.x...x..   
..x...x...xxx   
...xxxxxx....   
x............ 

आप देख सकते हैं, वहाँ कुछ द्वीपों जो बंद हो जाती हैं, यानी अगर कुछ नाव अपने क्षेत्र के अंदर है, यह बाहर निकलने के लिए सक्षम नहीं होगा, पूर्व के लिए कर रहे हैं:

..xxxxx.  
..x...x.   
..x.x.x.   
..x...x. 
..xxxxx. 

और गणना howm द्वीपों में से किसी भी खुले हैं, और कितने हैं, से अधिक आयु वालों की तरह एक दिया NxM नक्शे के लिए:

.xxxxx   
.x...x   
.x.x.x   
.xxx.x  

समस्या यह है: वहाँ कुछ खुला द्वीपों जो उनमें से बाहर निकलने के लिए संभव है, पूर्व कर रहे हैं बन्द है।

मैं दोहराता हूं: मैं नहीं चाहता कि आप इसे हल करें, बस कुछ परेशानियों, हल करने के लिए विचारों की आवश्यकता है। धन्यवाद

Answer 1

मुझे लगता है कि पुराने पुराने बाढ़ भरने वाले एल्गोरिदम का उपयोग करना आपको बताएगा कि अगर किसी बिंदु से आप किसी अन्य बिंदु तक पहुंच सकते हैं।

http://en.wikipedia.org/wiki/Flood_fill

इसके अलावा, आप आप के अंदर और बाहर (मुझे लगता है कि) द्वारा क्या मतलब है बेहतर परिभाषित करने की आवश्यकता हो सकती है।

Answer 2

बस सभी बिंदुओं से कनेक्ट किए गए ग्राफ को बनाएं (कनेक्ट होने पर उन्हें चिह्नित करें) और जब समाप्त हो जाए - जांचें कि ग्राफ़ नोड्स में से कोई भी परिधि में है या नहीं। फिर अगले अनमार्कित डॉट पर जाएं।

कुछ सामान्य ज्ञात एल्गोरिदम एक जुड़ा ग्राफ़ बनाने के लिए कर रहे हैं ....

Answer 3

आप इसे एक मैट्रिक्स में पढ़ सकते हैं, और उसके बाद के लिए खोज। या एक्स, और जब आप पाते हैं। या एक्स, एक रिकर्सिव फ़ंक्शन चलाएं जो आसन्न कनेक्शन की खोज करता है। जब आप समाप्त करते हैं, तो अगले के लिए खोजें। या एक्स जिसका अभी तक विश्लेषण नहीं किया गया है और दोहराया गया है।

Answer 4

मुझे लगता है कि करीब से आप एक द्वीप का मतलब है जिसमें समुद्र के कम से कम एक वर्ग होते हैं, जिससे कोई नक्शा की सीमा तक नहीं पहुंच सकता है; और खुले से आप वहां किसी भी अन्य द्वीप का मतलब है।

तो, सबसे पहले पता लगाएं कि कौन सी समुद्री टाइल नक्शा की सीमाओं से पहुंच योग्य है - सीमा पर किसी भी समुद्र टाइल से बाढ़ भरने और आप जिन लोगों को पास करते हैं उन्हें चिह्नित करके। यदि सीमा पर कोई समुद्र टाइल छोड़ी गई है, तो वहां से बाढ़ भरना जारी रखें।

अब जब आपने सीमा से पहुंचने वाली सभी टाइल चिह्नित की हैं, तो अन्य सभी समुद्री टाइल भूमि से घिरे हुए हैं। द्वीप के संबंधित टाइलों को चिह्नित करने के लिए आप द्वीप के उन सभी में से एक को ढूंढ सकते हैं (भूमि का पता लगाने तक उत्तर में जाकर), और भूमि टाइल पर बाढ़ भरने का उपयोग करें।

इस तरह आप समुद्री टाइलों को बंद करने वाले द्वीपों की गणना कर सकते हैं - "बंद" द्वीप।

प्रत्येक भूमि टाइल अनमार्कित छोड़ा गया "खुले" द्वीप से संबंधित है। उनको गिनने के लिए फिर से बाढ़ भरें।

Answer 5

यहाँ कुछ सरल लेबलिंग नियम हैं:

• जल है तो खुले या बंद
• एज खुले पानी
• जल को खोलने के लिए पानी के लिए खुला है अगले

Answer 6

बाढ़ एल्गोरिथ्म, या है बीएफएस