जांचें कि क्या पायथन में दो दी गई लंबाई की छलांग लगाकर किसी संख्या तक पहुंचना संभव है

मान लीजिए कि हम प्रारंभिक स्थिति p पर हैं, हम किसी भी दिशा (बाएं या दाएं) d1 और d2 इकाइयों पर कूद सकते हैं। हमें p से कूद कर स्थिति q पर पहुँचने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट p =5, q =10, d1 =4, d2 =3 जैसा है, तो आउटपुट 3 होगा क्योंकि हम दो बार दूरी 4 का उपयोग करके दाईं ओर जा सकते हैं, फिर हम स्थान 13 पर पहुंच सकते हैं, फिर बाएं कूदें 10 तक पहुंचने के लिए 3 इकाइयां.

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

• gcd_res :=d1 और d2 का gcd
• यदि (p - q) gcd_res से विभाज्य नहीं है, तो
  • वापसी -1
• que :=एक डबल एंडेड कतार परिभाषित करें
• विज़िट किया :=एक नया सेट
• एक जोड़ी (p, 0) को कतार में सम्मिलित करें
• पी को विज़िट किया गया के रूप में चिह्नित करें
• जबकि क्यू का आकार> 0 गैर-शून्य है, करें
  • (बिंदु, चरण) :=कतार का अगला तत्व और इसे कतार से हटा दें
  • यदि बिंदु q के समान है, तो
    • वापसी का चरण
  • यदि बिंदु + d1 का दौरा नहीं किया जाता है, तो
    • क्यू में एक जोड़ी (बिंदु + d1, चरण + 1) डालें
    • देखे गए के रूप में चिह्नित करें (बिंदु + d1)
  • यदि बिंदु + d2 का दौरा नहीं किया गया है तो गैर-शून्य है, तो
    • क्यू में एक जोड़ी (बिंदु + d2, चरण + 1) डालें
    • देखे गए के रूप में चिह्नित करें (बिंदु + d2)
  • यदि बिंदु - d1 नहीं देखा गया है तो गैर-शून्य है, तो
    • क्यू में एक जोड़ी (बिंदु - d1, चरण + 1) डालें
    • देखे गए के रूप में चिह्नित करें (बिंदु - d1)
  • यदि बिंदु - d2 नहीं देखा गया है तो गैर-शून्य है, तो
    • क्यू में एक जोड़ी (बिंदु - d2, चरण + 1) डालें
    • देखे गए के रूप में चिह्नित करें (बिंदु - d2)

उदाहरण

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

from math import gcd
from collections import deque
def solve(p, d1, d2, q):
   gcd_res = gcd(d1, d2)
   if (p - q) % gcd_res != 0:
      return -1
   que = deque()
   visited = set()
   que.appendleft([p, 0])
   visited.add(p)
   while len(que) > 0:
      pair = que.pop()
      point, step = pair[0], pair[1]
      if point == q:
         return step
      if point + d1 not in visited:
         que.appendleft([(point + d1), step + 1])
         visited.add(point + d1)
      if point + d2 not in visited:
         que.appendleft([(point + d2), step + 1])
         visited.add(point + d2)
      if point - d1 not in visited:
         que.appendleft([(point - d1), step + 1])
         visited.add(point - d1)
      if point - d2 not in visited:
         que.appendleft([(point - d2), step + 1])
         visited.add(point - d2)
p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))

इनपुट

5, 4, 3, 10

आउटपुट

True