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

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

इसलिए, यदि इनपुट px =1, py =1, qx =2, qy =3, पथ =[[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 है।

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

एक फंक्शन हेल्पर () को परिभाषित करें। इसमें k
- कोने:=एक नया सेट जिसमें जोड़े (px, py) और (qx, qy) शामिल हैं
- प्रत्येक x के लिए, y स्थिति k तक के पथ में, करें
  - जोड़े (x, y) को शीर्षों में जोड़ें
- trav:=एक नया डेक जिसमें युग्म (px, py) शामिल है
- जबकि ट्रैव खाली नहीं है, करें
  - जोड़ी (x, y) :=ट्रैव से सबसे बाईं ओर का आइटम पॉप करें
  - यदि (x, y) (qx, qy) के समान है, तो
    - सही लौटें
  - प्रत्येक kx के लिए, ky in ((x - 1, y),(x + 1, y), (x, y – 1), (x, y + 1)), do
    - यदि युग्म (kx, ky) शीर्षों में मौजूद है, तो
      - यात्रा के अंत में जोड़ी (kx, ky) डालें
      - शीर्षों से जोड़ी (kx, ky) हटाएं
  - झूठी वापसी
ll :=-1
ul :=पथों का आकार + 1
जबकि ll + 1
k :=ll + ((ul - ll) / 2) का न्यूनतम मान
यदि सहायक (के) सत्य है, तो
- उल:=के
अन्यथा,
- ll :=k

उल लौटें अगर उल <=पथ का आकार, अन्यथा वापसी -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]]