C++ এ চেসবোর্ডে নাইট সম্ভাবনা

ধরুন আমাদের একটি NxN চেসবোর্ড আছে, একজন নাইট r-th সারি এবং c-th কলাম থেকে শুরু করে এবং ঠিক K চালনা করার চেষ্টা করে। এখানে সারি এবং কলামগুলি 0 সূচীযুক্ত, তাই উপরের-বাম বর্গটি হল (0, 0), এবং নীচে-ডান বর্গটি হল (N-1, N-1)।

একটি নাইট একটি কোষ থেকে 8টি ভিন্ন কোষে চলাচল করতে পারে, যা এই চিত্রটিতে দেখানো যেতে পারে -

প্রতিবার নাইটটি সরানোর সময়, এটি এলোমেলোভাবে আটটি সম্ভাব্য চালের মধ্যে একটি বেছে নেয়। নাইটটি চলতে থাকে যতক্ষণ না এটি ঠিক K নড়াচড়া করে বা চেসবোর্ড থেকে সরে না যায়। আমাদের সম্ভাব্যতা খুঁজে বের করতে হবে যে নাইটটি নড়াচড়া বন্ধ করার পরে বোর্ডে থাকে।

সুতরাং ইনপুট যদি 3, 2, 0, 0 এর মত হয়, তাহলে আউটপুট হবে 0.0625। এর কারণ হল দুটি চাল (থেকে (1,2), (2,1)) যা নাইটটিকে বোর্ডে রাখবে। এখন সেই অবস্থানগুলির প্রতিটি থেকে, দুটি চালও রয়েছে যা নাইটটিকে বোর্ডে রাখবে। তাই এখানে বোর্ডে নাইট থাকার মোট সম্ভাবনা হল 0.0625।

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

এক দিক বিন্যাস নির্দেশ করুন, এটি [[-2,-1], [-2, 1], [2,-1], [2, 1], [1,2], [1, -2], [-1,2], [-1,-2]]
পুনরাবৃত্ত পদ্ধতি সমাধান () সংজ্ঞায়িত করুন, এটি x, y, n, k, এবং 3d অ্যারে dp লাগবে
যদি x>=n বা y>=n বা x <0 বা y <0, তারপর 0 ফেরত দিন
যদি k 0 হয়, তাহলে 1 ফেরত দিন
যদি dp[k,x,y] -1 না হয়, তাহলে dp[k,x,y] ফেরত দিন
dp[k, x, y] :=0
আমি 0 থেকে 7 রেঞ্জের জন্য
- dp[k,x,y] :=সমাধান(x+dir[i,0], y + dir[i, 1], n, k – 1, dp)
রিটার্ন dp[k,x,y]
মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
আকারের একটি 3d অ্যারে তৈরি করুন (k + 1) x N x N। এটি পূরণ করুন – 1
রিটার্ন সলভ(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));
}

ইনপুট

আউটপুট

0.0625