Probability of Knight to remain in the chessboard | C ++ program to find the probability of the Knight to remain inside the chessboard after taking exactly K number of steps ; size of the chessboard ; direction vector for the Knight ; returns true if the knight is inside the chessboard ; Bottom up approach for finding the probability to go out of chessboard . ; dp array ; for 0 number of steps , each position will have probability 1 ; for every number of steps s ; for every position ( x , y ) after s number of steps ; for every position reachable from ( x , y ) ; if this position lie inside the board ; store the result ; return the result ; Driver Code ; number of steps ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  8 NEW_LINE int dx [ ] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 } ; int dy [ ] = { 2 , 1 , -1 , -2 , -2 , -1 , 1 , 2 } ; bool inside ( int x , int y ) { return ( x >= 0 and x < N and y > = 0 and y < N ) ; } double findProb ( int start_x , int start_y , int steps ) { double dp1 [ N ] [ N ] [ steps + 1 ] ; for ( int i = 0 ; i < N ; ++ i ) for ( int j = 0 ; j < N ; ++ j ) dp1 [ i ] [ j ] [ 0 ] = 1 ; for ( int s = 1 ; s <= steps ; ++ s ) { for ( int x = 0 ; x < N ; ++ x ) { for ( int y = 0 ; y < N ; ++ y ) { double prob = 0.0 ; for ( int i = 0 ; i < 8 ; ++ i ) { int nx = x + dx [ i ] ; int ny = y + dy [ i ] ; if ( inside ( nx , ny ) ) prob += dp1 [ nx ] [ ny ] [ s - 1 ] / 8.0 ; } dp1 [ x ] [ y ] [ s ] = prob ; } } } return dp1 [ start_x ] [ start_y ] [ steps ] ; } int main ( ) { int K = 3 ; cout << findProb ( 0 , 0 , K ) << endl ; return 0 ; }