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]]
एक पुनरावर्ती विधि solve() परिभाषित करें, जो 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
i = 0 से 7 तक:
- 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); 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.knightProbability(3, 2, 0, 0)); 
}

इनपुट

3 2 0 0

आउटपुट

0.0625