import numpy as np
class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        directions = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]]
        dp = [[[0 for i in range(N)] for j in range(N)] for k in range(K + 1)]
        dp[0][r][c] = 1
        for step in range(1, K+1):
            for i in range(N):
                for j in range(N):
                    for ii, jj in directions:
                        x, y = i - ii, j - jj
                        if x<0 or x>=N or y<0 or y>=N:
                            continue
                        else:
                            dp[step][i][j] += dp[step-1][x][y]*0.125
        
        return sum(sum(np.array(dp[K])))