एक ग्रिड पर वर्गों का पता लगाने के लिए जो ब्लॉक जोड़ने के बाद कभी भी सबसे कम पथ का हिस्सा नहीं हो सकता है?

Question

मेरे पास एक शुरुआत, खत्म, और कुछ दीवारों के साथ एक ग्रिड है। इकाइयों के माध्यम से गुजरने के बिना, इकाइयों को सबसे कम पथ (केवल ऊपर/नीचे/बाएं/दाएं स्थानांतरित करना) प्रारंभ से लेकर खत्म तक ले जाएं।

उपयोगकर्ता के रूप में कई अतिरिक्त दीवारों को जोड़ने के लिए के रूप में वे पथ को बदलना चाहते हैं की अनुमति है।

हालांकि, ध्यान दें कि कोई फर्क नहीं पड़ता कि कितने दीवारों जोड़ रहे हैं या जहां वे जोड़ दिया जाता है, वहाँ कुछ वर्गों कि कम से कम पथ का हिस्सा बनने के लिए कभी नहीं कर सकते हैं कर रहे हैं!

इन वर्गों कभी नहीं कम से कम पथ का हिस्सा हो सकता है!

मैं यह पता लगाने का एक तरीका ढूंढ रहा हूं कि कौन से वर्ग कभी भी सबसे कम पथ का हिस्सा नहीं बन सकते हैं।

---

उपरोक्त मामलों को खोजने में काफी आसान है; लेकिन अधिक जटिल मामले हैं। पर विचार करें:

ऊपर छवि में, लाल डॉट्स के साथ वर्गों में से कोई भी कभी भी, सबसे अच्छा मार्ग का हिस्सा हो सकता है कि केवल एक ही क्षेत्र के लिए प्रवेश द्वार है वहाँ, और यह केवल दो रिक्त स्थान विस्तृत है, क्योंकि। यदि यह तीन रिक्त स्थान चौड़े थे, या यदि दीवारों में से किसी एक को हटा दिया गया था, तो उनमें से अधिकतर वर्ग शायद सबसे अच्छे मार्ग का हिस्सा हो सकते हैं।

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

Answer 1

एस से एफ तक किसी भी पथ पर विचार करें। यह पथ एक छोटा रास्ता हो सकता है (यदि आप हर दूसरे वर्ग को हटा देते हैं) जब तक कि आप केवल उन टाइलों का उपयोग करके "शॉर्टकट" नहीं ले सकते। यह तब होता है जब आपके पास दो आसन्न वर्ग होते हैं जो पथ में आसन्न नहीं होते हैं। तो आपको आसन्न वर्गों के सभी जोड़े पर विचार करने की आवश्यकता है; जो भी वे एस या एफ से डिस्कनेक्ट करते हैं (एफ से डिस्क को डिस्कनेक्ट किए बिना) एक छोटे से पथ का हिस्सा नहीं हो सकता है। साथ ही, एक वर्ग द्वारा डिस्कनेक्ट किए जा सकने वाले टाइल्स एस से एफ तक किसी भी पथ (जो कि दोहराना नहीं दोहराते हैं) का हिस्सा नहीं हो सकता है, इसलिए उन्हें भी जाना होगा।

एन को ग्रिड में वर्गों की संख्या होने दें। वर्गों की किसी विशेष जोड़ी के लिए (उनमें से ओ (एन) हैं), जो डिस्कनेक्ट हो जाता है, उसे बाढ़ के साथ ओ (एन) समय में गणना की जा सकती है, इसलिए यह ओ (एन^2) है। जो कि मिनी-कट से सस्ता है, जिसका आपने उल्लेख किया है, इसलिए मुझे लगता है कि यह आपके लिए काफी सस्ता है।

Answer 2

पहले हम देखते हैं कि, क्षेत्रों एक या दो आसन्न ग्रिड द्वारा अवरुद्ध किया जा सकता किसी भी कम से कम पथ में कभी नहीं होगा।

अपने उदाहरण में मामला देखें, यह उन दो पीले ग्रिड हैं जो डॉट्स को अवरुद्ध करते हैं।

एक ग्रिड द्वारा अवरुद्ध समझने में आसान है। जब दो द्वारा अवरुद्ध:

1. यदि सन्निकट नहीं है, हम इसे केवल पथ बनाने के लिए, में जाना एक के माध्यम से और एक दूसरे से बाहर जाने के लिए अतिरिक्त दीवारों जोड़ सकते हैं, तो हम अंदर लोगों पड़ सकता है।
2. आसन्न होने पर, हम हमेशा एक से सीधे दूसरे तक जा सकते हैं, इसलिए हम को अभी भी उस क्षेत्र के अंदर ग्रिड की आवश्यकता नहीं है।

तो यहाँ है एल्गोरिथ्म आता है:

की गणना प्रत्येक खाली ग्रिड

1. उस पर एक दीवार डाल दिया और का उपयोग बाढ़ भरण अवरुद्ध क्षेत्रों को खोजने के लिए, वे किसी काम का नहीं है।
2. अपने चार आसन्न ग्रिड (यदि खाली हो) में से एक पर दीवार डालने का प्रयास करें, तो अवरुद्ध क्षेत्रों को खोजने के लिए बाढ़ भरने का उपयोग करें, उनका कोई उपयोग नहीं है।