পাইথনে প্রদত্ত দুটি দৈর্ঘ্যের লাফ দিয়ে একটি সংখ্যায় পৌঁছানো সম্ভব কিনা তা পরীক্ষা করুন

ধরুন আমরা p শুরুর অবস্থানে আছি, আমরা যেকোন দিকে (বাম বা ডান) d1 এবং d2 ইউনিটে লাফ দিতে পারি। p থেকে লাফিয়ে q অবস্থানে পৌঁছানোর জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় p =5, q =10, d1 =4, d2 =3, তাহলে আউটপুট হবে 3 কারণ আমরা দূরত্ব 4 ব্যবহার করে দুবার ডানে লাফ দিতে পারি তারপর আমরা 13 অবস্থানে পৌঁছতে পারি, তারপরে বাম দিকে ঝাঁপ দিতে পারি। 3 ইউনিট 10 এ পৌঁছাতে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• gcd_res :=d1 এবং d2 এর gcd
• যদি (p - q) gcd_res দ্বারা বিভাজ্য না হয়, তাহলে
  • রিটার্ন -1
• que :=একটি ডবল শেষ সারি সংজ্ঞায়িত করুন
• পরিদর্শন করেছেন :=একটি নতুন সেট
• সারিতে একটি জোড়া (p, 0) ঢোকান
• p কে পরিদর্শন করা হয়েছে হিসাবে চিহ্নিত করুন
• যদিও que> 0 এর সাইজ অ-শূন্য, do
  • (পয়েন্ট, ধাপ) :=সারির সামনের উপাদান এবং এটিকে que থেকে মুছে দিন
  • বিন্দু যদি 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