पायथन में दिए गए बिंदुओं के माध्यम से वर्तमान स्थिति से कोई बिंदु पहुंच योग्य है या नहीं जांचने का प्रोग्राम

मान लीजिए 2D स्थान में एक पॉइंटर बिंदु p पर स्थित है जिसके निर्देशांक (px, py) हैं। अब पॉइंटर को दूसरे बिंदु q पर जाना है जिसके निर्देशांक (qx, qy) हैं। पॉइंटर स्वतंत्र रूप से नहीं चल सकता, यह q पर तभी जा सकता है यदि बीच में कुछ बिंदु स्थित हों। हमें बिंदुओं की एक सरणी paths दी गई है जिसमें विभिन्न निर्देशांक बिंदु हैं। पॉइंटर वर्तमान स्थिति से (x+1, y) या (x, y+1) या (x-1, y) या (x, y-1) पर स्थित बिंदु पर जा सकता है। सरणी paths में दिए गए बिंदुओं को क्रमिक रूप से संसाधित किया जाना चाहिए, जिसका अर्थ है कि सरणी में प्रत्येक बिंदु को कुल पथ में जोड़ा जाना चाहिए भले ही चाल न की जा सके। इसलिए, दिए गए प्रारंभिक और गंतव्य बिंदुओं को देखते हुए, हमें यह पता लगाना है कि पॉइंटर दिए गए बिंदुओं से गंतव्य तक पहुंच सकता है या नहीं। यदि यह पहुंच सकता है, तो हम गंतव्य तक पहुंचने के लिए पार किए गए बिंदुओं की कुल संख्या प्रिंट करते हैं; और यदि यह नहीं पहुंच सकता तो हम -1 प्रिंट करते हैं।

इसलिए, यदि इनपुट है px = 1, py = 1, qx = 2, qy = 3, paths = [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]], तो आउटपुट होगा 4।

यदि हम बिंदुओं को क्रमिक रूप से संसाधित करते हैं, तो हमें मिलता है:

बिंदु (1, 2): चाल चली गई, वर्तमान पॉइंटर स्थिति (1, 2)। पार किए गए बिंदु: 1।
बिंदु (0, 1): कोई चाल नहीं चली, वर्तमान पॉइंटर स्थिति (1, 2)। पार किए गए बिंदु: 2।
बिंदु (0, 2): कोई चाल नहीं चली, वर्तमान पॉइंटर स्थिति (1, 2)। पार किए गए बिंदु: 3।
बिंदु (1, 3): चाल चली गई, वर्तमान पॉइंटर स्थिति (1, 3)। पार किए गए बिंदु: 4।

गंतव्य वर्तमान पॉइंटर स्थिति से (x+1, y) स्थान पर स्थित है, इसलिए पार किए गए बिंदुओं की कुल संख्या 4 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

helper() फ़ंक्शन परिभाषित करें। यह k लेगा:
- vertices := एक नया सेट जिसमें जोड़े (px, py) और (qx, qy) हों
- paths में स्थिति k तक प्रत्येक x, y के लिए, करें:
  - जोड़े (x, y) को vertices में जोड़ें
- trav := एक नया डीक्यू जिसमें जोड़ा (px, py) हो
- जब trav खाली न हो, करें:
  - जोड़ा (x, y) := trav से सबसे बायां आइटम निकालें
  - यदि (x, y) (qx, qy) के समान है, तो:
    - True लौटाएं
  - ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)) में प्रत्येक kx, ky के लिए, करें:
    - यदि जोड़ा (kx, ky) vertices में मौजूद है, तो:
      - जोड़े (kx, ky) को trav के अंत में डालें
      - जोड़े (kx, ky) को vertices से हटाएं
- False लौटाएं
ll := -1
ul := paths का आकार + 1
जब ll + 1 < ul, करें:
- k := ll + floor((ul - ll) / 2)
- यदि helper(k) True है, तो:
  - ul := k
- अन्यथा:
  - ll := k
यदि ul <= paths का आकार, तो ul लौटाएं, अन्यथा -1 लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

from collections import deque
def solve(px, py, qx, qy, paths):
    def helper(k):
        vertices = {(px, py), (qx, qy)}
        for x, y in paths[:k]:
            vertices.add((x, y))
        trav = deque([(px, py)])
        while trav:
            x, y = trav.popleft()
            if (x, y) == (qx, qy):
                return True
            for kx, ky in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                if (kx, ky) in vertices:
                    trav.append((kx, ky))
                    vertices.remove((kx, ky))
        return False
    ll, ul = -1, len(paths) + 1
    while ll + 1 < ul:
        k = ll + (ul - ll) // 2
        if helper(k):
            ul = k
        else:
            ll = k
    return ul if ul <= len(paths) else -1
print(solve(1, 1, 2, 3, [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]]))

इनपुट

1, 1, 2, 3, [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]]