পাইথনে বাড়িতে পৌঁছানোর জন্য ন্যূনতম জাম্প খুঁজে বের করার প্রোগ্রাম

ধরুন নিষিদ্ধ নামক একটি অ্যারে আছে, যেখানে নিষিদ্ধ[i] নির্দেশ করে যে বাগটি নিষিদ্ধ [i] অবস্থানে যেতে পারে না, এবং আমাদের তিনটি মানও আছে a, b, এবং x। একটি বাগের বাড়ি নম্বর লাইনে x অবস্থানে রয়েছে। এটি প্রাথমিকভাবে 0 অবস্থানে রয়েছে। এটি নিয়ম অনুসরণ করে লাফ দিতে পারে -

বাগ ঠিক একটি অবস্থান ডানদিকে লাফ দিতে পারে৷
৷
বাগ ঠিক বি পজিশনে বাম দিকে যেতে পারে।
বাগ পরপর দুবার পিছনের দিকে ঝাঁপ দিতে পারে না।
বাগ অ্যারেতে দেওয়া কোনো নিষিদ্ধ অবস্থানে যেতে পারে না৷
৷
বাগ তার বাড়ির বাইরে এগিয়ে যেতে পারে, কিন্তু এটি নেতিবাচক মান সহ সংখ্যাযুক্ত অবস্থানে যেতে পারে না।

আমাদের গন্তব্যে পৌঁছানোর জন্য বাগটির জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক জাম্প খুঁজে বের করতে হবে। যদি এমন কোন সম্ভাব্য ক্রম না থাকে, তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি নিষিদ্ধ =[2,3,7,9, 12], a =4, b =2, x =16 এর মত হয়, তাহলে আউটপুট হবে 7 কারণ, 0 থেকে শুরু করে, a =4 এগিয়ে যান 4 এবং 8-এ পৌঁছানোর জন্য দুবার, কিন্তু 12-এ লাফানো যাবে না কারণ এটি নিষিদ্ধ, তারপর b =2 এ 6 তে পিছিয়ে যান, তারপর 10, 14, 18-এ লাফ দিন এবং তারপর 16-এ পৌঁছানোর জন্য দুটি পিছিয়ে যান, তাই 7টি ধাপ রয়েছে। পি>

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

সারি :=একটি টিপল সহ একটি সারি (x,0,True), নিষিদ্ধ :=একটি নতুন সেট এবং নিষিদ্ধ তালিকা থেকে উপাদান সন্নিবেশ করান
lim :=a + b + (সর্বাধিক x এবং নিষিদ্ধ সেটের সর্বোচ্চ মান)
সারি খালি না থাকার সময়, করুন
- (curr,jumps,is_b) :=সারি থেকে প্রথম উপাদান এবং সারি থেকে এটি সরান
- যদি curr নিষিদ্ধ হয় বা (0 <=curr <=lim) মিথ্যা হয়, তাহলে
  - পরবর্তী পুনরাবৃত্তির জন্য যান
- নিষিদ্ধ মধ্যে curr ঢোকান
- যদি curr 0 এর মত হয়, তাহলে
  - রিটার্ন জাম্পস
- যদি is_b সত্য হয়, তাহলে
  - সারিতে ঢোকান (curr+b,jumps+1,False)
- সারিতে ঢোকান (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