Explained two solutions: DP recursive and flattened
Intuition\nGame theory minimax with optimal play from both sides - Alice maximizes total moves while Bob minimizes. Key insight: Each captured pawn state can\'t
# Intuition\nGame theory minimax with optimal play from both sides - Alice maximizes total moves while Bob minimizes. Key insight: Each captured pawn state can\'t be revisited, making it perfect for DP with bitmask.\n\n# Approach\nBoth solutions build on same foundation:\n1. Precompute all knight-move distances between positions using BFS\n2. State represented as `[turn][pawns_bitmask][current_pos]`\n3. Main invariant: `dp[turn][mask][pos]` = optimal total moves when:\n   - Current player\'s turn (0=Alice, 1=Bob)\n   - Remaining pawns represented by mask\n   - Knight at position pos\n\nTwo implementations:\n1. Top-down: DFS + memoization\n2. Bottom-up: Iterative DP with same state space\n\n# Complexity\n- Time: $$O(2^P * P * P)$$ - Each state requires trying each remaining pawn\n- Space: $$O(2^P * P)$$ - For DP table\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        return maxMoves_dp_rec_memo(kx, ky, positions);\n        return maxMoves_dp_flatten(kx, ky, positions);\n    }\n\nprivate:\n    static constexpr int kInf = numeric_limits<int>::max() / 3;\n    static constexpr int tAlice = 0;\n    static constexpr int tBob = 1;\n    static constexpr int kPlayers = 2;\n\n    // First approach: Top-down DP with memoization\n    int maxMoves_dp_rec_memo(int kx, int ky, vector<vector<int>>& positions) {\n        const int S = 50;\n        const int N = S * S;\n\n        const int P = positions.size();\n        const int PC = 1 << P;\n\n        // Calculate shortest paths between all pairs of positions using BFS\n        vector<pair<int, int>> dxy = {  {-2, -1}, {-2,  1},  {-1, -2}, {-1,  2},\n                                        { 1, -2}, { 1,  2},  { 2, -1}, { 2,  1},\n                                     };\n        positions.push_back({kx, ky});\n        dist.resize(P + 1);\n        for (int i = 0; i < positions.size(); ++i) {\n            vector<vector<int>> d(S, vector<int>(S, kInf));\n            d[positions[i][0]][positions[i][1]] = 0;\n            queue<pair<int, int>> q;\n            q.emplace(positions[i][0], positions[i][1]);\n            while (!q.empty()) {\n                auto [x, y] = q.front();\n                q.pop();\n                for (const auto [dx, dy] : dxy) {\n                    int xx = x + dx, yy = y + dy;\n                    if (xx >= 0 && xx < S && yy >= 0 && yy < S) {\n                        if (d[xx][yy] == kInf) {\n                            d[xx][yy] = d[x][y] + 1;\n                            q.emplace(xx, yy);\n                        }\n                    }\n                }\n            }\n\n            dist[i].resize(P + 1);\n            for (int j = 0; j < positions.size(); ++j)\n                dist[i][j] = d[positions[j][0]][positions[j][1]];\n        }\n\n        // Initialize memoization table\n        // State: [player turn][remaining pawns bitmask][current position]\n        dp.assign(kPlayers, vector<vector<int>>(PC, vector<int>(P + 1, -1)));\n        return dfs(tAlice, PC - 1, P);\n    }\n\n    // [ turn: tAlice / tBob ] [ remain pawn bmask 0..PMALL ] [ pos 0..P ]\n    vector<vector<vector<int>>> dp;\n    vector<vector<int>> dist;\n\n    int dfs(int turn, int mask, int p) {\n        int& mres = dp[turn][mask][p];\n        if (mres > -1) return mres;\n        if (mask == 0) return mres = 0;  // Base case: no pawns left\n        // Initialize result based on player (max for Alice, min for Bob)\n        int res = turn == 0 ? -kInf : kInf;\n        for (int q = 0; q < dist.size() - 1; ++q) if (q != p && ( mask & (1 << q) )) {\n            int qmask = mask ^ (1 << q); // Remove captured pawn\n            int turns_count = dist[p][q] + dfs(turn ^ 1, qmask, q);\n            if (turn == tAlice) // Update result based on player\'s objective\n                res = max(res, turns_count);\n            else\n                res = min(res, turns_count);\n        }\n        return mres = res;\n    }\n\n    // Second approach: Bottom-up DP with flattened states\n    int maxMoves_dp_flatten(int kx, int ky, vector<vector<int>>& positions) {\n        const int S = 50;\n        const int N = S * S;\n\n        const int P = positions.size();\n        const int PC = 1 << P;\n\n        vector<pair<int, int>> dxy = {  {-2, -1}, {-2,  1},  {-1, -2}, {-1,  2},\n                                        { 1, -2}, { 1,  2},  { 2, -1}, { 2,  1},\n                                     };\n        positions.push_back({kx, ky});\n        vector<vector<int>> dist(P + 1);\n        for (int i = 0; i < positions.size(); ++i) {\n            vector<vector<int>> d(S, vector<int>(S, kInf));\n            d[positions[i][0]][positions[i][1]] = 0;\n            queue<pair<int, int>> q;\n            q.emplace(positions[i][0], positions[i][1]);\n            while (!q.empty()) {\n                auto [x, y] = q.front();\n                q.pop();\n                for (const auto [dx, dy] : dxy) {\n                    int xx = x + dx, yy = y + dy;\n                    if (xx >= 0 && xx < S && yy >= 0 && yy < S) {\n                        if (d[xx][yy] == kInf) {\n                            d[xx][yy] = d[x][y] + 1;\n                            q.emplace(xx, yy);\n                        }\n                    }\n                }\n            }\n\n            dist[i].resize(P + 1);\n            for (int j = 0; j < positions.size(); ++j)\n                dist[i][j] = d[positions[j][0]][positions[j][1]];\n        }\n\n        // [ turn: tAlice / tBob ] [ remain pawn bmask 0..PMALL ] [ pos 0..P ]\n        vector<vector<vector<int>>> dp(kPlayers, vector<vector<int>>(PC, vector<int>(P + 1)));\n        // Iterate through all possible states\n        for (int mask = 0; mask < PC; ++mask) {\n            for (int t = 0; t < kPlayers; ++t) {\n                for (int p = 0; p <= P; ++p) {\n                    if (mask == 0) { // Base case\n                        dp[t][mask][p] = 0;\n                        continue;\n                    }\n                    // Initialize result based on player\n                    dp[t][mask][p] = t == tAlice ? -kInf : kInf;\n                    // Try capturing each remaining pawn\n                    for (int q = 0; q < P; ++q) if (q != p && ( mask & (1 << q) )) {\n                        int qmask = mask ^ (1 << q);\n                        int turns_count = dist[p][q] + dp[t ^ 1][qmask][q];\n                        if (t == tAlice) // Update result based on player\'s objective\n                            dp[t][mask][p] = max(dp[t][mask][p], turns_count);\n                        else\n                            dp[t][mask][p] = min(dp[t][mask][p], turns_count);\n                    }\n                }\n            }\n        }\n\n        return dp[tAlice][PC - 1][P];\n    }\n};\n\n```
['C++']