Moving Robots - (Expectation)

Question

Problem

Each square of an $8\times8$ chessboard has a robot. Each robot independently moves $k$ steps, and there can be many robots on the same square.

On each turn, a robot moves one step left, right, up or down, but not outside the board. It randomly chooses a direction among those where it can move.

Your task is to calculate the expected number of empty squares after $k$ turns.

Constraints

$1≤k≤100$

Input:

The only input line has an integer $k$. 10

Output:

Print the expected number of empty squares rounded to six decimal places. 23.120740

my progress so far - by using dynamic prog. i figured out the expected number of robots on every cell after k iterations?

2dmatrix D

for 1 <= _ <= k
{
    
    2dmatrix newD
    
    for 1 <= i <= 8
    {
        for 1 <= j <= 8
        {
            // number_of_moves - possible directions the robot can go from current position
            number_of_moves = (i > 1) + (i < 8) + (j > 1) + (j < 8)

            // try going down
            if (i > 1)
                newD[i - 1][j] += (D[i][j] / number_of_moves)

            // and so on for the other 3 directions...
        }
    }
    
    D = newD

}

1. i felt this was a better forum for this question than stack overflow as its definitely very few lines of code and more math.

2. source - https://cses.fi/problemset/task/1726