688

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<double>> dp(n, vector<double>(n));
        dp[row][column] = 1.0;
        int dir[8][2] = {{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};

        for(; k>0; k--){
            vector<vector<double>> dp1(n, vector<double>(n));
            for(int r=0; r<n; r++){
                for(int c=0; c<n; c++){
                    for(int d=0; d<8; d++){
                        int nr = r+dir[d][0];
                        int nc = c+dir[d][1];
                        if(nr>=0 && nr<n && nc>=0 && nc<n){
                            dp1[nr][nc] += (dp[r][c]/8.0);
                        }
                    }
                }
            }
            swap(dp1, dp);
        }
        double ans = 0.0;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                ans += dp[i][j];
        return ans;
    }
};