C++ . में शतरंज की बिसात में नाइट की संभाव्यता

मान लीजिए कि हमारे पास एक NxN शतरंज की बिसात है, एक शूरवीर r-वें पंक्ति और c-वें स्तंभ से शुरू होता है और ठीक K चाल चलने का प्रयास करता है। यहां पंक्तियों और स्तंभों को 0 अनुक्रमित किया गया है, इसलिए शीर्ष-बाएं वर्ग (0, 0) है, और निचला-दायां वर्ग (N-1, N-1) है।

एक शूरवीर एक सेल से 8 अलग-अलग कोशिकाओं में घूम सकता है, जिसे इस आरेख में दिखाया जा सकता है -

हर बार जब शूरवीर को चलना होता है, तो वह बेतरतीब ढंग से आठ संभावित चालों में से एक को चुनता है। शूरवीर तब तक चलता रहता है जब तक कि वह बिल्कुल 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]]
पुनरावर्ती विधि हल () को परिभाषित करें, इसमें 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)
रिटर्न डीपी[के,एक्स,वाई]
मुख्य विधि से, निम्न कार्य करें
आकार की एक 3डी सरणी बनाएं (k + 1) x N x N. इसे - 1 से भरें
रिटर्न सॉल्व (आर, सी, एन, के, डीपी) / (8^के)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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