class Solution {
    
    public boolean isValid(int ni , int nj , int n ){

        if(ni < 0 || nj < 0 || ni >= n || nj >= n)
        return false;

        return true;
    }
    public double knightProbability(int n, int k, int row, int col) {
        /* Q48 in dp playlist ,current represent current instance of the board,
        next represent next instance of the board in the end we swap curr &
        next and make next to 0 again so that we can use it store the prob of
        next moves which will impact the board cells

        in the end we loop over the latest board and add all the probibilites
        on all cell which will give us probibility that knight remains on the 
        board
        */

        double[][] curr = new double[n][n];
        double[][] next = new double[n][n];

        //making a direction array to loop over for the knights 8 moves
        int[][] dir = {{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};

        //for the very first instance probibility of center cell will be 1
        curr[row][col] = 1;

        //looping for k moves
        for(int moves = 0 ; moves < k ; moves++){
            
        //looping the current board and storing effect of knight move on next
            for(int i = 0 ; i < n ; i++ ){

                for(int j = 0 ; j < n ; j++){
                    
                    if(curr[i][j] != 0){
                        int ni = 0 , nj = 0;    //next i , next j
                        for(int d = 0 ; d < 8 ; d++){
                            ni = i + dir[d][0];
                            nj = j + dir[d][1];

                            if(isValid(ni,nj,n))
                            next[ni][nj] += curr[i][j]/8.0;
                        }
                    }
                }
            }
        //to store the probibilities of next move we do the following 
            curr = next;
            next = new double[n][n];
        }

        //now we add all the probibilites of the latest board and return it 
        double prob = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++)
            prob += curr[i][j];
        }

        return prob;
    }
}