Here is the link to the question at CodeDrills:

There is a knight(chess piece) at every square of the N * N chess board and in each step each knight moves uniformly randomly to each square it can move within the board. Multiple knights are allowed on each square. Calculate expected number of empty squares after K steps. Find the value upto 6 digits of precision after the decimal point.

Note :- Knight movement in chess

Input Format Single line containing two space seperated integers N and K.

Output Format The required value upto 6 digits of precision after decimal point. The answer will be considered correct if the absolute difference between your answer and judge answer is within 10^-6

Constraints 4 <= N <= 20 1 <= K <= 10^6

Sample Input 0 4 1

Sample Output 0 5.361111111111111

Sample Explanation Expected value of number of empty squares after one step is equal to sum of probabilities of each square to be empty in one step.

Let's define P(x, y, u, v) as prob that a knight in square (x,y) doesn't move to square (u, v).

For example let's consider the square (1,1)

The probability for this square to be empty in one step = P(2, 3, 1, 1) * P(3, 2, 1, 1)

P(2, 3, 1, 1) = 3/4 (Because there are 4 possible moves for a knight at square (2, 3) and there is only one knight at (2, 3) initially)

Similarly P(3, 2, 1, 1) = 3/4

If we compute the probabilities for all the squares in a similar manner and sum them we get the above answer.

Help me in solving this problem...