BFS solution with memorization
The idea is to find the positions where knights will end up after K and then how many duplicate it contains.\nFor instance,\nN = 3\nK = 3\nr = 0\nc = 0\nIn the 
The idea is to find the positions where knights will end up after `K` and then how many duplicate it contains.\nFor instance,\nN = 3\nK = 3\nr = 0\nc = 0\nIn the first move, there are two places to go\n(2, 1), (1, 2) now `map` should be 1s on (2, 1) and (1, 2) since this can be visited once.\nIn the second move, since (2,1) and (1, 2) can visit (0, 0). `map` at (0, 0) will be 2 and (2, 0) = 1, (0, 2) = 1. Rest of them should be 0.\nIn the third move, there are (0, 0), (2, 0), (0, 2) in the queue. We know that any move from (0, 0), it adds up 2 instead of 1 because we had duplicate move.\nNow `map` (2,1) =3 (from (0, 0), (0, 2)), (1, 2) =3 (from (0, 0), (2, 0)), (0,1) = 1, (1, 0) = 1 and rest of array is 0. \n\nNote: This is not so fast.\n```\nclass Solution {\n    private final int[][] deltas = new int[][]{{-2, -1}, {-2, 1}, {2, 1}, {2, -1}, {1, -2}, {1, 2}, {-1, 2}, {-1, -2}};\n    public double knightProbability(int N, int K, int r, int c) {\n        Queue<int[]> queue = new LinkedList<>();\n        queue.add(new int[]{r, c});\n        double[][] map = new double[N][N];\n        for (int i = 0; i < N; ++i) {\n            Arrays.fill(map[i], 1);\n        }\n        for (int i = 0; i < K; ++i) {\n            int size = queue.size();\n            double[][] tmp = new double[N][N];\n            for (int j = 0; j < size; ++j) {\n                int[] move = queue.remove();\n                for (int[] delta: deltas) {\n                    int nr = move[0] + delta[0];\n                    int nc = move[1] + delta[1];\n                    if (isValid(N, nr, nc)) {\n                        if (tmp[nr][nc] == 0) {\n                            queue.add(new int[]{nr, nc});\n                        }\n                        tmp[nr][nc] += map[move[0]][move[1]];\n\n                    }\n                }\n            }\n            map = tmp;\n        }\n        double totalMoves = Math.pow(8, K);\n        double validMoves = 0;\n        for (int i = 0; i < N; ++i) {\n            for (int j = 0; j < N; ++j) {\n                validMoves += map[i][j];\n            }\n        }\n        double ret = validMoves / totalMoves;\n        return ret > 1.0 ? 1.0 : ret;\n    }\n    \n    private boolean isValid(int N, int r, int c) {\n        return r >= 0 && r < N && c >= 0 && c < N;\n    }\n}\n```
[]