👏90~100% Beats 27th Feb'25 - Dynamic Programming
IntuitionThe problem involves a strategic game where Alice and Bob alternate turns moving a knight to capture pawns on a 50x50 chessboard, with Alice aiming to
# Intuition
The problem involves a strategic game where Alice and Bob alternate turns moving a knight to capture pawns on a 50x50 chessboard, with Alice aiming to maximize the total number of moves and Bob seeking to minimize them. My initial thoughts were:

- The knight's movement requires calculating shortest paths, making BFS a suitable choice for the 50x50 grid.
- The game’s competitive nature, with opposing goals, points to a minimax strategy.
- The knight’s position after each capture influences subsequent moves, suggesting that state tracking is critical.
- Pre-computing distances between all key positions could optimize performance by avoiding repeated calculations.
- Memoization will be essential to cache results and prevent redundant exploration of identical game states.

# Approach
1. Pre-compute Distances:
- Perform BFS from the knight’s starting position `(kx, ky)` and each pawn’s position to all other relevant points (knight and pawns).
- Store these distances in a matrix `dist[i][j]`, where i=0 represents the knight’s initial position, and i=1 to n represent pawn positions, with j following the same indexing.
- This preprocessing step eliminates the need for on-the-fly BFS during the game simulation, saving significant time.
2. Dynamic Programming with Minimax:
- Define the state as `(pos, mask)`, where:
    - `pos` is the index of the knight’s current position (0 for the initial knight position, 1 to n for pawn positions after captures).
    - `mask` is a bitmask where each bit represents whether a pawn remains uncaptured (1) or has been taken (0).
    - For Alice’s turn (maximizing player): evaluate all possible pawn captures and choose the one yielding the highest total moves.
    - For Bob’s turn (minimizing player): evaluate all possible pawn captures and select the one resulting in the lowest total moves.
    - Use memoization to store results for each (pos, mask) state in a 2D table to avoid recomputation.
3. Algorithm:
- Start by pre-computing the distance matrix for all pairwise combinations of the knight and pawns.
- Initiate a recursive DFS from the knight’s starting position (pos=0) with all pawns available (mask = 2^n - 1).
- For each turn, compute the optimal move count by:
    - Iterating through all remaining pawns in the mask.
    - Looking up the pre-computed move count to reach each pawn.
    - Recursively calculating the best outcome for the next player.
- Return the maximum total moves Alice can achieve under optimal play.

# Complexity
- Time complexity:
    - Pre-computation:
        - Dijkstra's algorithm is run from n+1 starting points (1 knight + n pawns).
        - Each Dijkstra's algorithm explores up to $50*50 = 2500$ cells in the worst case.
        - Priority queue operations: $O(logV)$ per insertion/extraction, where $V = 2500$
        - Total: $((n+1) * 2500 * log(2500)) ≈ O(n * 10^4)$ operations.

    - DFS: $O(n^2 ⋅ 2^n)$
        - There are $(n+1)$ positions x $2^n$ possible mask states.
        - For each state, loops over remaining bits in mask: $O(n)$.
        - Distance lookups are $O(1)$ due to pre-computation.
        - Total states: $(n+1) * 2^n$, with $O(n)$ work per state.

- Space Complexity:
    - Distance Matrix: $O((n+1)^2) ≈ O(n^2)$
        - Stores (n+1) x (n+1) distances for knight and n pawns.
    - Memoization Table: $O(n ⋅ 2^n)$
        - Stores results for $(n+1)$ positions × $2^n$ mask combinations.


# Code
```cpp []
using namespace std;

class Solution {
public:
    const int moves[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
                            {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
    
    int dp[17][1 << 16];

    vector<vector<int>> precomputeDistances(int kx, int ky, vector<vector<int>>& positions) {
        int n = positions.size();
        vector<vector<int>> dist(n + 1, vector<int>(n + 1, INT_MAX));
        vector<pair<int, int>> points(n + 1);
        points[0] = {kx, ky};
        for (int i = 0; i < n; i++) points[i + 1] = {positions[i][0], positions[i][1]};

        // Use BFS instead of Dijkstra’s for unweighted graph
        for (int i = 0; i <= n; i++) {
            vector<vector<bool>> visited(50, vector<bool>(50, false));
            queue<tuple<int, int, int>> q; // {x, y, distance}
            int sx = points[i].first, sy = points[i].second;
            q.push({sx, sy, 0});
            visited[sx][sy] = true;

            while (!q.empty()) {
                auto [x, y, d] = q.front();
                q.pop();

                // Check if this is a target point
                for (int j = 0; j <= n; j++) {
                    if (dist[i][j] == INT_MAX && x == points[j].first && y == points[j].second) {
                        dist[i][j] = d;
                    }
                }

                // Early termination: if all distances from i are found
                bool allFound = true;
                for (int j = 0; j <= n; j++) {
                    if (dist[i][j] == INT_MAX) {
                        allFound = false;
                        break;
                    }
                }
                if (allFound) break;

                for (auto& m : moves) {
                    int nx = x + m[0], ny = y + m[1];
                    if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.push({nx, ny, d + 1});
                    }
                }
            }
        }
        return dist;
    }

    int dfs(int pos, int mask, bool aliceTurn, vector<vector<int>>& dist) {
        if (mask == 0) return 0;
        if (dp[pos][mask] != -1) return dp[pos][mask];

        int bestScore = aliceTurn ? INT_MIN : INT_MAX;
        int n = __builtin_popcount(mask);

        int tempMask = mask;
        while (tempMask) {
            int i = __builtin_ctz(tempMask);
            tempMask &= (tempMask - 1);

            int moves = dist[pos][i + 1];
            if (moves == INT_MAX) continue;

            int nextScore = moves + dfs(i + 1, mask & ~(1 << i), !aliceTurn, dist);

            if (aliceTurn) {
                bestScore = max(bestScore, nextScore);
                // Prune: If Alice finds a large enough score
                if (bestScore >= n * 50) break; // Max possible moves ≈ n * board diagonal
            } else {
                bestScore = min(bestScore, nextScore);
                if (bestScore <= 0) break; // Bob can force 0
            }
        }

        return dp[pos][mask] = bestScore;
    }

    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
        int n = positions.size();
        if (n == 0) return 0;

        vector<vector<int>> dist = precomputeDistances(kx, ky, positions);
        memset(dp, -1, sizeof(dp));
        return dfs(0, (1 << n) - 1, true, dist);
    }
};
```repetitive calculations, using bitmask dynamic programming to track remaining pawns, leveraging minimax to capture Alice's maximization versus Bob's minimization, and ensuring scalability for standard input sizes (n ≤ 15) within time constraints.

['C++']