Simple Approach || BitMask DP || Pre-Computation || BFS
Approach\n# 1. Precompute Distances Using BFS:\nUse global static variable to ensure the flag is initialised once.\n\nUse BFS to precompute and calculate the sh
# Approach\n# 1. Precompute Distances Using BFS:\nUse global static variable to ensure the flag is initialised once.\n\nUse BFS to precompute and calculate the shortest distance from any point on the chessboard to all other points.\nThis gives us the distance matrix dist where dist[x1][y1][x2][y2] represents the shortest path from (x1, y1) to (x2, y2).\n\n# 2. Recursive DP Function:\n\nDefine a recursive function f(curr, mask, turn) where curr is the index of the current pawn being considered, mask represents the set of captured pawns, and turn indicates whose turn it is (Alice or Bob).\n\nIf it\u2019s Alice\u2019s turn, maximize the score considering all possible moves.\nIf it\u2019s Bob\u2019s turn, minimize the score considering all possible moves.\n\n\n# Code\n```cpp []\n#include <vector>\n#include <queue>\n#include <climits>\n#include <cstring>\nusing namespace std;\n\nint dist[50][50][50][50]; // 4D array to store distances between all pairs of points on the board\nint dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}; // Possible moves in x-direction for a knight\nint dy[8] = {2, 1, -1, -2, -2, -1, 1, 2}; // Possible moves in y-direction for a knight\n\n// Function to compute shortest distances from (startx, starty) to all other points\nvoid dis(int startx, int starty) {\n    queue<pair<pair<int, int>, int>> q; // Queue to perform BFS: (current position, distance)\n    q.push({{startx, starty}, 0});\n    dist[startx][starty][startx][starty] = 0; // Distance from a point to itself is zero\n\n    while(!q.empty()) {\n        int x = q.front().first.first; // Current x-coordinate\n        int y = q.front().first.second; // Current y-coordinate\n        int d = q.front().second; // Distance from start point\n        q.pop();\n\n        for(int i = 0; i < 8; i++) {\n            int newx = x + dx[i]; // New x-coordinate after move\n            int newy = y + dy[i]; // New y-coordinate after move\n            // Check if new position is within bounds and has not been visited yet\n            if(newx >= 0 && newx < 50 && newy >= 0 && newy < 50 && dist[startx][starty][newx][newy] == -1) {\n                dist[startx][starty][newx][newy] = 1 + d; // Update distance\n                q.push({{newx, newy}, d + 1}); // Add new position to queue\n            }\n        }\n    }\n}\n\n// Function to preprocess distances for all pairs of points\nvoid pre() {\n    static bool flag = false; // use of static bool to initialise the flag once\n    if(flag) return; // Skip if already preprocessed\n    memset(dist, -1, sizeof(dist)); // Initialize distances to -1\n    for (int i = 0; i < 50; i++) {\n        for (int j = 0; j < 50; j++) {\n            // Compute distances from (i, j) if not already computed\n            if(dist[i][j][i][j] == -1) dis(i, j);\n        }\n    }\n    flag = 1; // Mark preprocessing as done\n}\n\nclass Solution {\npublic:\n    vector<vector<int>> memo; // Memoization table for storing intermediate results\n\n    // Recursive function to compute maximum/minimum score\n    int f(int curr, int mask, int turn, vector<vector<int>>& positions) {\n        int n = positions.size();\n        if(mask == (1 << n) - 1) return 0; // All positions visited, base case\n\n        // Check if result is already computed\n        if(memo[curr][mask] != -1) return memo[curr][mask];\n\n        int ans;\n        int x = positions[curr][0]; // Current x-coordinate\n        int y = positions[curr][1]; // Current y-coordinate\n\n        if(!turn) { // Alice\n            ans = INT_MIN; // Initialize to minimum value\n            for(int i = 0; i < n; i++) {\n                if(mask & (1 << i)) continue; // Skip if position already visited\n                int nextx = positions[i][0]; // Next x-coordinate\n                int nexty = positions[i][1]; // Next y-coordinate\n                int newDist = dist[x][y][nextx][nexty]; // Distance to next position\n                // Compute maximum score by taking the maximum of all possible moves\n                ans = max(ans, newDist + f(i, mask | (1 << i), !turn, positions));\n            }\n        } else { // Bob\n            ans = INT_MAX; // Initialize to maximum value\n            for(int i = 0; i < n; i++) {\n                if(mask & (1 << i)) continue; // Skip if position already visited\n                int nextx = positions[i][0]; // Next x-coordinate\n                int nexty = positions[i][1]; // Next y-coordinate\n                int newDist = dist[x][y][nextx][nexty]; // Distance to next position\n                // Compute minimum score by taking the minimum of all possible moves\n                ans = min(ans, newDist + f(i, mask | (1 << i), !turn, positions));\n            }\n        }\n\n        return memo[curr][mask] = ans;\n    }\n\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        positions.push_back({kx, ky}); // Add knight\'s starting position to the list\n        int n = positions.size(); // Total number of positions\n        pre(); // Preprocess distances\n        memo.resize(n, vector<int>(1 << n, -1)); // Initialize memoization table\n        return f(n-1, (1<<(n-1)), 0, positions); // Start recursion with knight\'s position\n    }\n};\n\n\n```
['Dynamic Programming', 'Breadth-First Search', 'Bitmask', 'C++']