class Solution:
    def bfs(self, N: int, K: int, r: int, c: int):
        moves = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (-1, -2), (1, -2), (2, -1), (2, 1)]
        q = []
        q.append((r, c, 1)) # (i, j, prob)
        for _ in range(K):
            tmp = dict()
            for _ in range(len(q)):
                (i, j, prob) = q.pop(0)
                for mi, mj in moves:
                    if 0 <= i + mi < N and 0 <= j + mj < N:
                        if (i+mi, j+mj) in tmp:
                            tmp[(i+mi, j+mj)] += prob / 8
                        else:
                            tmp[(i+mi, j+mj)] = prob / 8

            for k,v in tmp.items():
                q.append((k[0], k[1], v))
        return sum([x[2] for x in q])


    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        return self.bfs(N, K, r, c)