बिटमैप में "छेद" की संख्या

Question

एक एमएक्सएन बिटमैप पर विचार करें जहां कक्ष 0 या 1. '1' का मतलब है और '0' का अर्थ खाली है।

बिटमैप में 'छेद' की संख्या पाएं, जहां एक छेद खाली कोशिकाओं का एक संगत क्षेत्र है।

उदाहरण के लिए, इस दो छेद है:

11111 
10101 
10101 
11111 

... और यह केवल एक है:

11111 
10001 
10101 
11111 

क्या सबसे तेज़ तरीका है, जब एम और एन दोनों 1 और के बीच हो रहा है 8?

स्पष्टीकरण: विकर्णों को केवल पक्ष-आसन्न मामलों के अनुरूप नहीं माना जाता है।

नोट: मुझे कुछ ऐसा लगता है जो डेटा प्रारूप का लाभ उठाता है। मुझे पता है कि इसे कैसे एक ग्राफ में बदलना है और [बीडी] एफएस इसे लेकिन यह ओवरकिल लगता है।

Answer 1

आपको अपनी छवि पर connected component labeling करने की आवश्यकता है। आप उपरोक्त लिंक किए गए विकिपीडिया आलेख में वर्णित Two-pass algorithm का उपयोग कर सकते हैं। आपकी समस्या के छोटे आकार को देखते हुए, One-pass algorithm पर्याप्त हो सकता है।

आप BFS/DFS का भी उपयोग कर सकते हैं लेकिन मैं उपरोक्त एल्गोरिदम की अनुशंसा करता हूं।

Answer 2

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

तो बस सेट

की संख्या की गणना

Answer 3

वहाँ मेज लुकअप और बिटवाइज़ संचालन का उपयोग करके प्राप्त की फायदे हो सकते हैं।

उदाहरण के लिए 256 तत्व तालिका में 8 पिक्सेल की पूरी लाइन देखी जा सकती है, इसलिए फ़ील्ड 1xN में छेद की संख्या एकल लुकअप द्वारा प्राप्त की जाती है। फिर 256xK तत्वों की कुछ लुकअप तालिका हो सकती है, जहां के पिछले पंक्ति में छेद कॉन्फ़िगरेशन की संख्या है, पूर्ण छेद और अगली छेद कॉन्फ़िगरेशन की संख्या को contatining। यह सिर्फ एक विचार है।