পাইথনে শतरঞ্জের বোর্ডে ঘোড়া (knight) k মুভে বোর্ডে থাকার পেরসেন্টেজ বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে চারটি মান n, x, y, এবং k আছে। এখানে n নির্দেশ করে n x n আকারের একটি চেসবোর্ড এবং x, y কোয়ার্ডিনেট নির্দেশ করে ঘোড়া (knight) (x, y) পজিশনে আছে। ঘোড়াকে ঠিক kটি স্টেপ নিতে হবে, যেখানে প্রতিটি স্টেপে সে ৮টি দিকের যেকোনো একটি যেতে পারে সমান সম্ভাবনায়। আমাদের কাজ হল k মুভ নেওয়ার পর ঘোড়া বোর্ডের ভিতরে থাকার পেরসেন্টেজ চান্স (নিকটতম ইন্টিজার) বের করা। শর্ত হল একবার বোর্ডের বাইরে চলে গেলে সে আবার বোর্ডে ফিরে আসতে পারবে না।

উদাহরণস্বরূপ, যদি ইনপুট হয় n = 8, (x=0, y=0), k=1, তবে আউটপুট হবে 50, কারণ ৮x৮ বোর্ডে ঘোড়ার প্রাথমিক পজিশন (১,১)। এক স্টেপ নিলে ৮টি পজিশনের মধ্যে ৪টিতে বোর্ডের ভিতরে থাকবে, বাকি ৪টিতে বাইরে যাবে। তাই ৫০%।

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

মувের তালিকা বানান: [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
একটি dfs() ফাংশন ডিফাইন করুন যা x, y, k নেবে।
- যদি (x,y) বোর্ডের রেঞ্জে না থাকে, তবে 0 রিটার্ন করুন।
- যদি k == 0 হয়, তবে 1 রিটার্ন করুন।
- s := [] (খালি তালিকা)
- সব (dx, dy) মুভের জন্য:
  - x = dfs(x+dx, y+dy, k-1) / 8
  - x কে s-তে ঢুকান
- s-এর সব এলিমেন্টের যোগফল রিটার্ন করুন।
মূল মেথড থেকে round(dfs(x, y, k) * 100) রিটার্ন করুন (নিকটতম ইন্টিজার)।

উদাহরণ কোড

moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

class Solution:
    def solve(self, n, x, y, k):
        def dfs(x, y, k):
            if x < 0 or y < 0 or x >= n or y >= n:
                return 0
            if k == 0:
                return 1
            return sum(dfs(x + dx, y + dy, k - 1) / 8 for dx, dy in moves)
        return int(dfs(x, y, k) * 100)

ob = Solution()
n = 8
x = 1
y = 1
k = 1
print(ob.solve(n, x, y, k))

ইনপুট

8, 1, 1, 1

আউটপুট