🔥 BFS + DP 🧠 Chessboard Problem 🏆 Java Solution 😎
LeetCode Solution: Maximum Moves Calculation\n\n## Intuition\nTo solve the problem of calculating the maximum number of moves a knight can make on a chessboard 
# LeetCode Solution: Maximum Moves Calculation\n\n## Intuition\nTo solve the problem of calculating the maximum number of moves a knight can make on a chessboard to visit a series of given positions, we need to utilize a combination of breadth-first search (BFS) and dynamic programming. The idea is to compute the shortest paths between positions and use memoization to optimize the solution.\n\n## Approach\n1. **Breadth-First Search (BFS)**:\n   - Implement BFS to calculate the shortest path from one position to another on a chessboard. This is used to determine distances between all positions.\n\n2. **Distance Matrix**:\n   - Create a distance matrix that holds the shortest distances between all pairs of positions including the starting point (knight\'s initial position) and each of the target positions.\n\n3. **Dynamic Programming with Bitmasking**:\n   - Use dynamic programming (DP) with bitmasking to find the optimal sequence of visiting the positions.\n   - Use a recursive helper function to compute the maximum score based on the current state of visited positions and whose turn it is.\n\n4. **Memoization**:\n   - Store previously computed results to avoid redundant calculations and improve efficiency.\n\n## Complexity\n- **Time Complexity**: `O(2^n * n^2)`\n  - Where `n` is the number of positions. The bitmasking approach has `2^n` possible states, and for each state, we perform `O(n^2)` operations for distance calculations and recursive calls.\n- **Space Complexity**: `O(2^n * n)`\n  - Space is needed for memoization and the distance matrix.\n\n## Code\n```java\nclass Solution {\n    int[][] DIRECTIONS = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};\n    int[][] dist;\n    int[][] memo;\n    int np;\n\n    int bfs(int startX, int startY, int targetX, int targetY) {\n        boolean[][] vis = new boolean[50][50];\n        Queue<int[]> q = new LinkedList<>();\n        q.offer(new int[] {startX, startY, 0});\n        vis[startX][startY] = true;\n        while (!q.isEmpty()) {\n            int[] cur = q.poll();\n            int x = cur[0], y = cur[1], moves = cur[2];\n\n            if (x == targetX && y == targetY) {\n                return moves;\n            }\n\n            for (int[] dir : DIRECTIONS) {\n                int nx = x + dir[0], ny = y + dir[1];\n                if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && !vis[nx][ny]) {\n                    vis[nx][ny] = true;\n                    q.offer(new int[] {nx, ny, moves + 1});\n                }\n            }\n        }\n\n        return Integer.MAX_VALUE; \n    }\n\n    int helper(int mask, int last, boolean turn) {\n        if (mask == (1 << np) - 1) {\n            return 0;\n        }\n\n        if (memo[mask][last] != -1) {\n            return memo[mask][last];\n        }\n\n        int res;\n        if (turn) {\n            res = Integer.MIN_VALUE; \n            for (int next = 0; next < np; next++) {\n                if ((mask & (1 << next)) == 0) {\n                    res = Math.max(res, dist[last][next] + helper(mask | (1 << next), next, false));\n                }\n            }\n        } else {\n            res = Integer.MAX_VALUE; \n            for (int next = 0; next < np; next++) {\n                if ((mask & (1 << next)) == 0) { \n                    res = Math.min(res, dist[last][next] + helper(mask | (1 << next), next, true));\n                }\n            }\n        }\n\n        memo[mask][last] = res;\n        return res;\n    }\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        np = positions.length;\n        dist = new int[np + 1][np];\n        memo = new int[1 << np][np];\n\n        for (int i = 0; i < (1 << np); i++) {\n            Arrays.fill(memo[i], -1);\n        }\n\n        for (int i = 0; i < np; i++) {\n            dist[np][i] = bfs(kx, ky, positions[i][0], positions[i][1]);\n        }\n\n        for (int i = 0; i < np; i++) {\n            for (int j = i + 1; j < np; j++) {\n                int d = bfs(positions[i][0], positions[i][1], positions[j][0], positions[j][1]);\n                dist[i][j] = d;\n                dist[j][i] = d;\n            }\n        }\n\n        int res = Integer.MIN_VALUE;\n        for (int i = 0; i < np; i++) {\n            res = Math.max(res, dist[np][i] + helper(1 << i, i, false));\n        }\n\n        return res;\n    }\n}\n
['Dynamic Programming', 'Bit Manipulation', 'Breadth-First Search', 'Memoization', 'Matrix', 'Bitmask', 'Java']