পাইথনে বাধা ও উল্টা জাম্প নিয়ম মেনে বাসায় পৌঁছাতে ন্যূনতম জাম্প বের করার প্রোগ্রাম

মান লিজিয়ে একটি অ্যারে আছে forbidden যেখানে forbidden[i] নির্দেশ করে পোকামachte সেখানে জাম্প দিতে পারবে না। আর তিনটি মান আছে a, b, x। পোকার বাসা অবস্থিত x পজিশনে। এটি শুরুতে ০-এ আছে। এটি নিচের নিয়ম অনুযায়ী জাম্প দিতে পারে:

ডানে ঠিক a পজিশন জাম্প দিতে পারে।
বামে ঠিক b পজিশন জাম্প দিতে পারে।
পরে পোরে দুবার উল্টা জাম্প দিতে পারবে না।
forbidden অ্যারেতে দেওয়া পজিশনে জাম্প দিতে পারবে না।
বাসার পরে জাম্প দিতে পারবে, কিন্তু নেগেটিভ পজিশনে যেতে পারবে না।

বাসায় পৌঁছাতে ন্যূনতম জাম্প সংখ্যা বের করতে হবে। সম্ভব না হলে -1 রিটার্ন করুন।

যেমন, ইনপুট হলে forbidden = [2,3,7,9,12], a = 4, b = 2, x = 16, তবে আউটপুট হবে 7 কারণ: ০ থেকে শুরু করে a=4 ডানে দুবার জাম্প দিয়ে ৪ এবং ৮-এ পৌঁছাল, কিন্তু ১২-এ যেতে পারল না (forbidden), তাই b=2 বামে জাম্প দিয়ে ৬-এ এসেছে, তারপর ১০, ১৪, ১৮ এবং দুবার বামে যেতে ১৬-এ পৌঁছেছে। মোট ৭ ধাপ।

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

queue := [(x, 0, True)], forbidden := set(forbidden)
lim := max(max(forbidden), x) + a + b
queue খালি না থাকা পর্যন্ত:
- (curr, jumps, is_b) := queue.pop(0)
- যদি curr in forbidden বা 0 <= curr <= lim নয়, তবে কন্টিনিউ করুন।
- forbidden.add(curr)
- যদি curr == 0 হয়, তবে jumps রিটার্ন করুন।
- যদি is_b সত্য হয়, তবে queue.append((curr+b, jumps+1, False))
- queue.append((curr-a, jumps+1, True))
-1 রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(forbidden, a, b, x):
    queue, forbidden = [(x, 0, True)], set(forbidden)
    lim = max(max(forbidden), x) + a + b
    while queue:
        curr, jumps, is_b = queue.pop(0)
        if curr in forbidden or not 0 <= curr <= lim:
            continue
        forbidden.add(curr)
        if curr == 0:
            return jumps
        if is_b:
            queue.append((curr + b, jumps + 1, False))
        queue.append((curr - a, jumps + 1, True))
    return -1

forbidden = [2,3,7,9,12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))

ইনপুট

[2,3,7,9,12], 4, 2, 16