পাইথনে একটি সাপ এবং মই খেলার সর্বনিম্ন চাল খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা সাপ এবং মই খেলা খেলছি। আমাদের একটি শর্ত আছে যে আমরা একটি পাশা উপর পছন্দ করতে পারেন যে কোনো নম্বর রোল করতে পারেন. আমরা পজিশন 0 থেকে শুরু করি এবং আমাদের গন্তব্য হল পজিশন 100, এবং আমরা গন্তব্যে পৌঁছানোর জন্য বেশ কয়েকবার ডাইস ঘুরাই। আমাদের অবশ্যই গন্তব্যে পৌঁছানোর জন্য প্রয়োজনীয় ডাইস রোলগুলির ন্যূনতম সংখ্যা খুঁজে বের করতে হবে যদি আমাদের বোর্ডে সাপ এবং মইয়ের অবস্থান সরবরাহ করা হয়। অ্যারে সাপ এবং মই বোর্ডে সাপ এবং মইয়ের অবস্থান এবং প্রতিটি প্রবেশের প্রতিনিধিত্ব করে। অ্যারেতে একটি প্রারম্ভিক মান এবং বোর্ডে একটি সাপ বা একটি মইয়ের একটি শেষ মান রয়েছে৷

সুতরাং, যদি ইনপুটটি হয় মই =[(11, 40), (37,67), (47, 73), (15, 72)], সাপ =[(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)], তাহলে আউটপুট হবে 8।

সাপ এবং মইয়ের অবস্থান অনুসারে বোর্ডে 100তম অবস্থানে পৌঁছানোর জন্য ন্যূনতম 8টি চাল প্রয়োজন৷

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

• অ্যারের মইয়ের সাথে অ্যারের সাপগুলি যুক্ত করুন
• কিনারা :=একটি নতুন মানচিত্র
• প্রতিটি জোড়ার জন্য f,t মই, do
  • কিনারা[f] :=t
• u :=একটি নতুন সেট
• v :=একটি নতুন সেট
• v-তে (1) যোগ করুন
• m :=0
• যদিও v তে 100 নেই, do
  • m :=m + 1
  • w :=একটি নতুন সেট
  • v এর প্রতিটি f এর জন্য, করুন
    • আমি 1 থেকে 6 রেঞ্জের জন্য, কর
      • n :=f + i
      • যদি n প্রান্তে থাকে, তাহলে
        • n :=প্রান্ত[n]
      • যদি u-তে n থাকে, তাহলে
        • পরবর্তী পুনরাবৃত্তির জন্য যান
      • এড(n) ইউতে
      • w-এর সাথে যুক্ত(n)
  • v :=w
• রিটার্ন m

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(ladders, snakes):
    ladders.extend(snakes)
    edges = {}
    for f,t in ladders:
        edges[f] = t
    u = set()
    v = set()
    v.add(1)
    m = 0
    while 100 not in v:
        m += 1
        w = set()
        for f in v:
            for i in range(1,7):
                n = f + i
                if n in edges:
                    n = edges[n]
                if n in u:
                    continue
                u.add(n)
                w.add(n)
        v = w
    return m
print(solve([(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

ইনপুট

[(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

আউটপুট

8