3283. Maximum Number of Moves to Kill All Pawns
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    private static final int[][] KNIGHT_MOVES = {\n            {2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}\n    };\n    private static final int CHESS_SIZE = 50;\n\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        int n = positions.length;\n        int[][] allPositions = new int[n + 1][2];\n        System.arraycopy(positions, 0, allPositions, 0, n);\n        allPositions[n] = new int[]{kx, ky};\n        Integer[][][] dp = new Integer[n + 1][CHESS_SIZE][CHESS_SIZE];\n        for (int i = 0; i <= n; i++) {\n            bfs(allPositions[i], dp[i]);\n        }\n        Integer[][] dp1 = new Integer[1 << (n + 1)][n + 1];\n\n        return solve(dp1, 1 << n, n, allPositions, dp);\n\n    }\n\n    private int solve(Integer[][] dp, int mask, int i, int[][] positions, Integer[][][] distDp) {\n        if (mask == (1 << positions.length) - 1) {\n            return 0;\n        }\n        if (dp[mask][i] != null) {\n            return dp[mask][i];\n        }\n\n        boolean turn = Integer.bitCount(mask) % 2 == 1;\n        int result = turn ? Integer.MIN_VALUE : Integer.MAX_VALUE;\n\n        for (int j = 0; j < positions.length; j++) {\n            if ((mask & (1 << j)) == 0) {\n                int dist = distDp[i][positions[j][0]][positions[j][1]];\n                if (turn) {\n                    result = Math.max(result, solve(dp, mask | (1 << j), j, positions, distDp) + dist);\n                } else {\n                    result = Math.min(result, solve(dp, mask | (1 << j), j, positions, distDp) + dist);\n                }\n            }\n        }\n        return dp[mask][i] = result;\n    }\n\n\n    private void bfs(int[] position, Integer[][] dp) {\n        Deque<int[]> deque = new ArrayDeque<>();\n        deque.offer(position);\n        dp[position[0]][position[1]] = 0;\n        while (!deque.isEmpty()) {\n            int[] pos = deque.poll();\n            for (int[] dir : KNIGHT_MOVES) {\n                int x = pos[0] + dir[0];\n                int y = pos[1] + dir[1];\n                if (isValidIndex(x) && isValidIndex(y) && dp[x][y] == null) {\n                    dp[x][y] = dp[pos[0]][pos[1]] + 1;\n                    deque.offer(new int[]{x, y});\n                }\n            }\n        }\n    }\n\n    private boolean isValidIndex(int i) {\n        return i >= 0 && i < CHESS_SIZE;\n    }\n\n}\n\n```
['Java']