एमएस पेंट कोड एक साक्षात्कार में पूछा गया

Question

मेरे पास आज एक साक्षात्कार था और इस सवाल से पूछा गया था!

एमएस पेंट प्रोग्राम कोड। एन * एन पिक्सल क्षेत्र। दिया गया पिक्सेल और रंग, रंग को पिक्सेल में वांछित रंग में बदलें और यदि आसन्न पिक्सल एक ही रंग के हैं तो उन्हें भी बदलें।

मैंने यह कहकर संपर्क किया कि मैं एक एन * एन सरणी ले जाऊंगा और दिए गए पिक्सेल की जांच करूँगा और आसन्न को ले जाऊंगा। उदाहरण के लिए दिया गया पिक्सेल एक्स है, यी पहले एक्स में वाई, वाई में रंग की जांच करेगा और अगला एक्स (1 +, वाई + 1), (एक्स + 1, वाई), (एक्स, वाई + 1)), (x-1, y-1), (x-1, y-1) ....

लेकिन साक्षात्कारकर्ता खुश नहीं था क्या कोई मुझे बेहतर एल्गोरिदम के साथ एक और तरीका सुझा सकता है .. जिसमें बेहतर स्थान है और समय जटिलता!

Answer 1

साक्षात्कारकर्ता शायद बाढ़ भरने के लिए कह रहा था, जिसे एक सरल दृष्टिकोण के साथ नहीं किया जा सकता है।

यदि यह बाढ़ भर जाता है, तो विकर्ण आसन्न के रूप में नहीं गिना जाता है।

सबसे सरल बाढ़ भरने सरणी पर प्रत्येक आसन्न पिक्सेल पर एक पुनरावर्ती कॉल है। एक बड़े ग्रिड पर सरल तरीके का उपयोग करना ढेर से बाहर होने की संभावना है।

सही स्थान को शुरू करने का सही तरीका है, फिर रिक्त करें, जांचें कि पिक्सेल रंग अभी भी स्रोत रंग है या नहीं, और बाएं और दाएं भरने के दौरान स्कैन करें, और ऊपर और नीचे सभी पिक्सल को एनक्यू करें। कतार सूखा होने तक जारी रखें।

Answer 2

जिस एल्गोरिदम के बारे में आप बात कर रहे हैं उसे बाढ़ भरने कहा जाता है। प्रसिद्ध दृष्टिकोण Wikipedia.

Answer 3

पर चर्चा कर रहे हैं आप इस समस्या को हल करने के लिए डीएफएस एल्गोरिथ्म का उपयोग कर सकते हैं। एक पिक्सेल (xi, यी) दिया गया है, आप हमेशा ग्राफ का निर्माण कर सकते हैं जैसे कि पिक्सेल नोड (xi-1, yi-1), (xi-1, yi), (xi, yi + 1), (xi + 1, यी), (xi + 1, यी -1), (xi + 1, यी + 1), (xi-1, यी + 1) और (xi, yi-1) आसन्न पिक्सेल नोड्स के रूप में (xi, yi) । निष्पादित करें डीएफएस नोड (xi, yi) से प्रत्येक नोड को रंग और बैकट्रैक में रंगने के बाद आप विभिन्न रंग नोड को दबाते हैं। डीएफएस में ओ (वी + ई) की एक अच्छी समय जटिलता है।