Java BFS solution
Although mang DP solutions are posted, I\'d like to post my BFS solution here.\n```java\npublic class Solution {\n\n    private int[][]dir = new int[][]{{-2,-1}
Although mang DP solutions are posted, I\'d like to post my BFS solution here.\n```java\npublic class Solution {\n\n    private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};\n\n    class Pair {\n        public int x;\n        public int y;\n\n        public Pair(int x, int y) {\n            this.x = x;\n            this.y = y;\n        }\n\n        @Override\n        public boolean equals(Object o) {\n            if (this == o) return true;\n            if (o == null || getClass() != o.getClass()) return false;\n            Pair pair = (Pair) o;\n            return x == pair.x && y == pair.y;\n        }\n        @Override\n        public int hashCode() {\n            return Objects.hash(x, y);\n        }\n\n    }\n\n    public double knightProbability(int N, int K, int r, int c) {\n        Map<Pair, Double> cur = new HashMap<>(), next = new HashMap<>();\n        cur.put(new Pair(r, c), 1.0);\n        int t = K;\n        while (t-- > 0) {\n            for (Map.Entry<Pair, Double> point : cur.entrySet()) {\n                int x = point.getKey().x, y = point.getKey().y;\n                double value = point.getValue();\n                for (int[] d : dir) {\n                    int i = x + d[0];\n                    int j = y + d[1];\n                    if (i < 0 || i > N - 1 || j < 0 || j > N - 1) {\n                        continue;\n                    }\n                    Pair tmp = new Pair(i, j);\n                    next.put(tmp, next.getOrDefault(tmp, 0.0) + value);\n                }\n            }\n            Map<Pair, Double> map = cur;\n            cur = next;\n            next = map;\n            next.clear();\n        }\n        double count = 0;\n        for (Double v : cur.values()) {\n            count += v;\n        }\n        return count / Math.pow(8, K);\n    }\n}
['Breadth-First Search']