ধরুন আমাদের একটি NxN চেসবোর্ড আছে, একটি ঘোড়া r-তম সারি এবং c-তম কলাম থেকে শুরু করে সঠিকভাবে K চলে যাওয়ার চেষ্টা করে। এখানে সারি এবং কলাম ০-ইন্ডেক্সড, তাই উপরের বাম কোণা (০, ০), এবং নিচের ডান কোণা (N-১, N-১)।
একটি ঘোড়া একটি কক্ষ থেকে ৮টি ভিন্ন কক্ষে যেতে পারে, যা এই ডায়াগ্রামে দেখানো হয়েছে −
প্রতিবার ঘোড়া যাওয়ার সময়, এটি আটটি সম্ভাব্য যাওয়ার中略 থেকে যাদুকরীভাবে একটি বেছে নেয়। ঘোড়া চলতে থাকে যতক্ষণ না এটি সঠিকভাবে K চলে যায় বা চেসবোর্ডের বাইরে চলে যায়। আমাদের বোর্ডে থাকার সম্ভাবনা বের করতে হবে।
তাই যদি ইনপুট হয় 3, 2, 0, 0, তবে আউটপুট হবে 0.0625। কারণ দুটি যাওয়া ( (1,2), (2,1) ) ঘোড়াকে বোর্ডে রাখবে। এখন সেই প্রতিটি অবস্থান থেকে, আরও দুটি যাওয়া ঘোড়াকে বোর্ডে রাখবে। তাই মোট সম্ভাবনা 0.0625।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- একটি দিক অ্যারে dir সংজ্ঞায়িত করুন, এটি হল [[-2,-1], [-2, 1],[2,-1], [2, 1], [1,2], [1,-2], [-1,2], [-1,-2]]
- একটি রিকার্সিভ মেথড solve() সংজ্ঞায়িত করুন, এটি x, y, n, k, এবং 3D অ্যারে dp নেবে
- যদি x >= n বা y >= n বা x < 0 বা y < 0, তবে ০ ফেরত দিন
- যদি k ০ হয়, তবে ১ ফেরত দিন
- যদি dp[k,x,y] -1 না হয়, তবে dp[k,x,y] ফেরত দিন
- dp[k, x, y] := ০
- i = 0 থেকে ৭ পর্যন্ত
- dp[k,x,y] := solve(x+dir[i,0], y + dir[i, 1], n, k – 1, dp)
- dp[k,x,y] ফেরত দিন
- মূল মেথড থেকে, নিম্নলিখিত কাজ করুন
- (k + 1) x N x N আকারের একটি 3D অ্যারে তৈরি করুন। এটি -1 দিয়ে পূরণ করুন
- solve(r, c, N, k, dp) / (8^K) ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}}; class Solution { public: double solve(int x, int y, int n, int k, vector < vector < vector < double > > >& dp){ if(x >= n || y >= n || x < 0 || y < 0 ) return 0.0; if(k == 0) return 1.0; if(dp[k][x][y] != -1) return dp[k][x][y]; dp[k][x][y] = 0; for(int i = 0; i < 8; i++){ dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp); } return dp[k][x][y]; } double knightProbability(int N, int K, int r, int c) { vector < vector < vector < double > > > dp (K + 1, vector < vector < double > >(N, vector < double >(N, -1))) ; return solve(r, c, N, K, dp) / pow(8, K); } }; main(){ Solution ob; cout << (ob.knightProbability(3, 2, 0, 0)); }ইনপুট
3 2 0 0
আউটপুট
0.0625
