Find The Probability of Knight C++ Program

Given an NxN chessboard and a Knight at position (x,y). The Knight has to take exactly K steps, where at each step it chooses any of the 8 directions uniformly at random. What is the probability that the Knight remains in the chessboard after taking K steps, with
the condition that it can’t enter the board again once it leaves it.

Constraints:
1<= T <=100
0<= N, K, X, Y <=100

Example:
Input:
1
8 0 0 3
Output:
0.125000

 

 

#include<bits/stdc++.h>
using namespace std;
double dp[100][100][100];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,x,y,k;
cin>>n>>x>>y>>k;

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
dp[i][j][0]=1;
}
for(int s=1;s<=k;s++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
double p=0.00;
if(i-2>=0 && j-1>=0)
p=p+dp[i-2][j-1][s-1]/8.00;

if(i-1>=0 && j-2>=0)
p=p+dp[i-1][j-2][s-1]/8.00;

if(i+2<n && j-1>=0)
p=p+dp[i+2][j-1][s-1]/8.00;

if(i+1<n && j-2>=0)
p=p+dp[i+1][j-2][s-1]/8.00;

if(i+2<n && j+1<n)
p=p+dp[i+2][j+1][s-1]/8.00;

if(i-2>=0 && j+1<n)
p=p+dp[i-2][j+1][s-1]/8.00;

if(i-1>=0 && j+2<n)
p=p+dp[i-1][j+2][s-1]/8.00;

if(i+1<n && j+2<n)
p=p+dp[i+1][j+2][s-1]/8.00;

dp[i][j][s]=p;

}
}
}
cout<<fixed<<setprecision(6)<<dp[x][y][k]<<endl;
}
return 0;
}

I you found that your code is not running or working properly Please comment.

Leave a Reply

Close Menu