Java Solution || beats 100%
Intuition\nThe problem is a strategic turn-based game involving a knight and multiple pawns on a large chessboard. The objective is to compute the maximum total
# Intuition\nThe problem is a strategic turn-based game involving a knight and multiple pawns on a large chessboard. The objective is to compute the maximum total number of moves that Alice can achieve while both players (Alice and Bob) play optimally. The game is all about capturing pawns, and in each move, the knight captures one pawn. Alice tries to maximize the total number of moves, while Bob tries to minimize them.\n\n- Knight\'s Movement: The knight has a unique movement pattern in chess, moving in an "L" shape. For any given position, it has up to 8 possible moves, and calculating the shortest path from one point to another on a chessboard is essential here.\n\n- Optimal Play: Alice and Bob both play optimally, with Alice trying to maximize the total number of moves and Bob minimizing them. This makes the game involve minimax-type decisions, where Alice tries to prolong the game by selecting pawns that take longer to reach, and Bob counters by picking pawns that require fewer moves.\n\n- Key Observations:\n\n1. Alice will always pick pawns that are farther away to maximize moves.\n2. Bob will always pick pawns that are closer to minimize moves.\n3. We need to simulate the optimal strategies of both players using a backtracking approach with minimax.\n\n# Approach\n1. Breadth-First Search (BFS) for Knight Moves:\n\n- Use BFS to calculate the shortest number of moves for the knight to reach each pawn. BFS is ideal for finding the shortest path on an unweighted grid like a chessboard since it explores all possible positions layer by layer.\n2. Recursive Minimax Approach:\n\n- The game involves alternating turns between Alice and Bob. Alice tries to maximize the total number of moves, and Bob tries to minimize them. This suggests the use of a minimax algorithm:\n  -   Alice\'s Turn (Maximizer): She will choose the pawn that takes the most moves to capture.\n   - Bob\'s Turn (Minimizer): He will choose the pawn that takes the fewest moves to capture.\n- Recursively simulate the game by considering all possible captures at each turn, and keep track of the total number of moves made.\n3. Edge Cases:\n\n- There could be only one pawn, in which case Alice captures it directly.\n- The game can have multiple pawns, and both players must decide optimally.\n\n\n# Complexity\n   -  Time complexity:\n     - BFS Complexity: Each BFS takes O(N^2), where \uD835\uDC41=50 is the size of the chessboard.\n     - Minimax Recursion: The number of recursive calls depends on the number of pawns p. For p pawns, there are \uD835\uDC5D!permutations of turns. This results in a worst-case time complexity of \uD835\uDC42(\uD835\uDC5D!\u22C5\uD835\uDC412)\n\n - Space complexity:\n   - BFS: O(n^2) = O(2500)\n   - Recursion (Minimax): O(p^2) - where p is <=15 so O(15^2)=O(225).\n   - Overall - O(n^2+p^2) = O(2500)\n\n# Code\n```java []\n\nclass Solution {\n    private static final int[][] KNIGHT_MOVES = {\n        {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},\n        {1, -2}, {1, 2}, {2, -1}, {2, 1}\n    };\n    private static final int BOARD_SIZE = 50;\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        int[][] distances = new int[positions.length][positions.length];\n        for (int i = 0; i < positions.length; i++) {\n            for (int j = 0; j < positions.length; j++) {\n                distances[i][j] = minMoves(positions[i][0], positions[i][1], positions[j][0], positions[j][1]);\n            }\n        }\n        \n        int[] initialDist = new int[positions.length];\n        for (int i = 0; i < positions.length; i++) {\n            initialDist[i] = minMoves(kx, ky, positions[i][0], positions[i][1]);\n        }\n        \n        return dfs(initialDist, distances, (1 << positions.length) - 1, -1, true, new HashMap<>());\n    }\n\n    private int dfs(int[] initialDist, int[][] distances, int mask, int last, boolean isAlice, Map<Long, Integer> memo) {\n        if (mask == 0) return 0;\n        \n        long key = ((long) mask << 33) | ((long) last << 1) | (isAlice ? 1 : 0);\n        if (memo.containsKey(key)) return memo.get(key);\n        \n        int res = isAlice ? Integer.MIN_VALUE : Integer.MAX_VALUE;\n        for (int i = 0; i < initialDist.length; i++) {\n            if ((mask & (1 << i)) != 0) {\n                int newMask = mask ^ (1 << i);\n                int dist = (last == -1) ? initialDist[i] : distances[last][i];\n                int subRes = dfs(initialDist, distances, newMask, i, !isAlice, memo);\n                if (isAlice) {\n                    res = Math.max(res, subRes + dist);\n                } else {\n                    res = Math.min(res, subRes + dist);\n                }\n            }\n        }\n        \n        memo.put(key, res);\n        return res;\n    }\n\n    private int minMoves(int startX, int startY, int endX, int endY) {\n        Queue<int[]> queue = new LinkedList<>();\n        boolean[][] visited = new boolean[BOARD_SIZE][BOARD_SIZE];\n        queue.offer(new int[]{startX, startY, 0});\n        visited[startX][startY] = true;\n\n        while (!queue.isEmpty()) {\n            int[] current = queue.poll();\n            int x = current[0], y = current[1], moves = current[2];\n\n            if (x == endX && y == endY) {\n                return moves;\n            }\n\n            for (int[] move : KNIGHT_MOVES) {\n                int newX = x + move[0];\n                int newY = y + move[1];\n                if (isValid(newX, newY) && !visited[newX][newY]) {\n                    queue.offer(new int[]{newX, newY, moves + 1});\n                    visited[newX][newY] = true;\n                }\n            }\n        }\n\n        return -1; // Should never reach here if input is valid\n    }\n\n    private boolean isValid(int x, int y) {\n        return x >= 0 && x < BOARD_SIZE && y >= 0 && y < BOARD_SIZE;\n    }\n}\n```
['Java']