ধরুন আমাদের চারটি মান আছে n, x, y, এবং k। এখানে n একটি n x n দাবাবোর্ড এবং x, y স্থানাঙ্ক নির্দেশ করে একটি নাইট (x, y) এ স্থাপন করা হয়েছে। নাইটকে ঠিক k পদক্ষেপ নিতে হবে, যেখানে প্রতিটি ধাপে এটি 8টি দিকগুলির মধ্যে যেকোনো একটি এলোমেলোভাবে সরাতে পারে। k চাল নেওয়ার পর নাইট যে দাবাবোর্ডে থাকে তার শতাংশের সুযোগ (নিকটতম পূর্ণসংখ্যা) আমাদের খুঁজে বের করতে হবে। আমাদের একটি শর্ত মানতে হবে যে এটি বোর্ড ছেড়ে চলে গেলে এটি আর প্রবেশ করতে পারবে না।
সুতরাং, যদি ইনপুটটি n =8, (x =0, y =0), k =1 এর মত হয়, তাহলে আউটপুট হবে 50, যেমন আমাদের এখানে 8x8 চেসবোর্ড আছে এবং নাইটের প্রাথমিক অবস্থান হল (1, 1) ) এটি k =1 ধাপ নিতে পারে। একটি পদক্ষেপ গ্রহণ করলে এটি 8টি অবস্থানের মধ্যে 4টি বোর্ডের ভিতরে শুয়ে থাকবে এবং অন্যান্য অবস্থানে বাইরে শুয়ে থাকবে। তাই 50%।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- চালের একটি তালিকা তৈরি করুন [(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
- s-এ x ঢোকান
- s-এ উপাদানগুলির যোগফল ফেরত দিন
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- (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
আউটপুট
0
