beats 100%
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```cpp []\n \n\nclass Solution { \npublic:\n// Directions for knight moves\nint dirs[8][2] = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};\n\n// Function to calculate the minimum moves from (kx, ky) to all positions using BFS\nvoid bfs(int startX, int startY, int index, int** dist, vector<pair<int, int>>& positions) {\n    vector<vector<int>> boardDist(50, vector<int>(50, -1));  // To store distances for BFS\n    queue<pair<int, int>> q;\n    q.push({startX, startY});\n    boardDist[startX][startY] = 0;\n    \n    while (!q.empty()) {\n        auto [x, y] = q.front();\n        q.pop();\n        \n        for (auto& dir : dirs) {\n            int nx = x + dir[0], ny = y + dir[1];\n            if (nx >= 0 && ny >= 0 && nx < 50 && ny < 50 && boardDist[nx][ny] == -1) {\n                boardDist[nx][ny] = boardDist[x][y] + 1;\n                q.push({nx, ny});\n            }\n        }\n    }\n    \n    // Fill the dist array for this pawn/knight\n    for (int i = 0; i < positions.size(); ++i) {\n        dist[index][i] = boardDist[positions[i].first][positions[i].second];\n    }\n}\n\n// DP function to compute max moves\nint solve(int** dist, int** dp, int idx, int mask, int n, bool alice_turn) {\n    if (mask == 0) return 0;  // No pawns left to capture\n    \n    if (dp[idx][mask] != -1) return dp[idx][mask];\n    \n    int res = (alice_turn ? -1 : 1e9);  // Maximize for Alice, minimize for Bob\n    \n    for (int i = 1; i <= n; ++i) {\n        if (mask & (1 << (i - 1))) {  // If pawn `i` is still available\n            int moves = dist[idx][i];  // Distance from current `idx` to pawn `i`\n            \n            if (alice_turn) {\n                // Alice tries to maximize the total moves\n                res = max(res, moves + solve(dist, dp, i, mask ^ (1 << (i - 1)), n, false));\n            } else {\n                // Bob tries to minimize the total moves\n                res = min(res, moves + solve(dist, dp, i, mask ^ (1 << (i - 1)), n, true));\n            }\n        }\n    }\n    \n    return dp[idx][mask] = res;\n}\n\nint maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n    int n = positions.size();\n    \n    // Create a new list to hold all positions, where 0 is the knight and 1..n are pawns\n    vector<pair<int, int>> allPositions;\n    allPositions.push_back({kx, ky});  // Knight\'s position\n    for (auto& pos : positions) {\n        allPositions.push_back({pos[0], pos[1]});\n    }\n    \n    // Allocate dist and dp arrays\n    int** dist = (int**)malloc((n + 1) * sizeof(int*));\n    for (int i = 0; i <= n; ++i) {\n        dist[i] = (int*)malloc((n + 1) * sizeof(int));\n    }\n    \n    int** dp = (int**)malloc((n + 1) * sizeof(int*));\n    for (int i = 0; i <= n; ++i) {\n        dp[i] = (int*)malloc((1 << n) * sizeof(int));\n        memset(dp[i], -1, (1 << n) * sizeof(int));  // Initialize DP table with -1\n    }\n    \n    // Run BFS for the knight and each pawn\n    bfs(kx, ky, 0, dist, allPositions);  // BFS for knight (index 0)\n    for (int i = 1; i <= n; ++i) {\n        bfs(positions[i-1][0], positions[i-1][1], i, dist, allPositions);  // BFS for each pawn\n    }\n    \n    // Start the DP from the knight\'s position, all pawns are available (mask = (1 << n) - 1)\n    int result = solve(dist, dp, 0, (1 << n) - 1, n, true);\n    \n    // Free allocated memory\n    for (int i = 0; i <= n; ++i) {\n        free(dist[i]);\n        free(dp[i]);\n    }\n    free(dist);\n    free(dp);\n    \n    return result;\n}\n\n};\n\n```
['C++']