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

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

যেমন, ইনপুট যদি p = 5, q = 10, d1 = 4, d2 = 3 হয়, তবে আউটপুট হবে ৩ কারণ আমরা ডান দিকে ৪ ইউনিট লাফ দিয়ে দুবার করলে ১৩-এ পৌঁছাব, তারপর বাম দিকে ৩ ইউনিট লাফ দিয়ে ১০-এ পৌঁছাব।

সমাধানের ধাপসমূহ

gcd_res := d1 এবং d2-এর GCD
যদি (p - q) gcd_res দ্বারা বিভাজ্য নয়, তবে:
- -1 রিটার্ন করুন
que := একটি ডবল-এন্ডেড কিউ (deque) সংজ্ঞায়িত করুন
visited := একটি নতুন সেট (set)
কিউ-তে একটি জোড়া (p, 0) ইনসার্ট করুন
p-কে ভিজিটেড (visited) হিসেবে মার্ক করুন
যখন que-র সাইজ ০-র চেয়ে বড়, করুন:
- (point, step) := কিউ-এর ফ্রন্ট এলিমেন্ট এবং কিউ-এ থেকে ডিলিট করুন
- যদি point q সমান হয়, তবে:
  - step রিটার্ন করুন
- যদি point + d1 ভিজিটেড নয়, তবে:
  - কিউ-তে (point + d1, step + 1) ইনসার্ট করুন
  - (point + d1)-কে ভিজিটেড হিসেবে মার্ক করুন
- যদি point + d2 ভিজিটেড নয়, তবে:
  - কিউ-তে (point + d2, step + 1) ইনসার্ট করুন
  - (point + d2)-কে ভিজিটেড হিসেবে মার্ক করুন
- যদি point - d1 ভিজিটেড নয়, তবে:
  - কিউ-তে (point - d1, step + 1) ইনসার্ট করুন
  - (point - d1)-কে ভিজিটেড হিসেবে মার্ক করুন
- যদি point - d2 ভিজিটেড নয়, তবে:
  - কিউ-তে (point - d2, step + 1) ইনসার্ট করুন
  - (point - 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