C++のチェス盤でのナイト確率

NxNチェス盤が1つあるとすると、騎士はr番目の行とc番目の列から開始し、正確にK回移動しようとします。ここでは、行と列に0のインデックスが付けられているため、左上の正方形は（0、0）であり、右下の正方形は（N-1、N-1）です。

騎士はセルから8つの異なるセルに移動できます。これは、この図に示されています-

騎士が移動するたびに、8つの可能な移動の1つをランダムに選択します。騎士は、正確にK移動するか、チェス盤から離れるまで移動を続けます。騎士が動きを止めた後もボードに留まる確率を見つける必要があります。

したがって、入力が3、2、0、0のような場合、出力は0.0625になります。これは、騎士をボードに留める2つの動き（（1,2）、（2,1）へ）があるためです。これらの位置のそれぞれから、騎士をボードに留めておく2つの動きもあります。したがって、ここでは、騎士がボードに留まる確率の合計は0.0625です。

これを解決するには、次の手順に従います-

• 一方向配列ディレクトリを定義します。これは[[-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
• 0から7の範囲のiの場合
  • dp [k、x、y]：=resolve（x + dir [i、0]、y + dir [i、1]、n、k – 1、dp）
• return dp [k、x、y]
• メインの方法から、次の手順を実行します
• サイズ（k + 1）x N x Nの3D配列を作成します。これに–1を入力します
• returnsolve（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