[DP] 2 Solutions | Brute Force, DP + Bitmask
Solution-1: Brute Force\n### Idea:\n+ Calculate the minimum number of moves required for the knight to capture each pawn for every possible sequence of captures
# Solution-1: Brute Force\n### Idea:\n+ Calculate the minimum number of moves required for the knight to capture each pawn for every possible sequence of captures. This involves generating all permutations of the pawns and calculating the total moves for each permutation.\n### Complexity:\n+ This approach is computationally expensive due to the factorial growth of permutations (O(n!)).\n\n# Solution-2: Bitmask DP\n### Idea:\n+ Calculate the maximum number of moves a knight can make to capture all pawns on a 50x50 chessboard, with Alice trying to maximize and Bob trying to minimize the total moves.\n\n1) **Preprocessing:** \n\t+ **Use BFS to calculate APSP**.\n\t\t+ Precompute the minimum moves required for the knight to travel between any two positions on the board.\n2) **Dynamic Programming (DP):** \n\t+ Use bitmask - to store positions of 16 pieces (15 pawn + 1 knight).\n\t+ Utilize a bitmask DP approach to simulate the game, considering both players\u2019 optimal strategies. The calculateMaxMoves function recursively determines the maximum moves by alternating turns between Alice and Bob.\n### Code:\n```\nconst int BOARD_SIZE = 50; // GIVEN.\nconst int INF = 1e9;\nconst int KNIGHT_MOVES[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};\n\n// Precomputed minimum moves for knight from any position to any other position\nvector<vector<int>> minMoves[BOARD_SIZE][BOARD_SIZE];\nint dp[2][16][1 << 16];\nbool isPreprocessed = false;\n\nclass Solution \n{\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) \n    {\n        return sol1BitMaskDP(kx, ky, positions);\n    }\n\nprivate:\n    // Main function to calculate the maximum moves starting from the knight\'s initial position\n    int sol1BitMaskDP(int knightRow, int knightCol, vector<vector<int>>& positions) \n    {\n        preprocess(); // Ensure preprocessing is done\n        vector<vector<int>> allPositions = {{knightRow, knightCol}};\n        allPositions.insert(allPositions.end(), positions.begin(), positions.end());\n        \n        int numPositions = allPositions.size();\n        memset(dp, -1, sizeof(dp)); // Initialize DP array\n        \n        return calculateMaxMoves(0, 0, 1, allPositions); // Start the recursive calculation\n    }\n\n    // Preprocess function to compute minimum moves for all positions on the board\n    // TC & SC: O(BOARD_SIZE^4).\n    void preprocess() \n    {\n        if ( isPreprocessed ) return;\n        isPreprocessed = true;\n        \n        for (int i = 0; i < BOARD_SIZE; ++i)\n            for (int j = 0; j < BOARD_SIZE; ++j)\n                minMoves[i][j] = calculateMinMoves(i, j);\n    }\n\n    // BFS -- APSP (All Pairs Shortest Path):\n    //      Function to calculate minimum moves from a given start position to all other positions using BFS.\n    // TC & SC: O(BOARD_SIZE^2).\n    vector<vector<int>> calculateMinMoves(int startRow, int startCol) \n    {\n        vector<vector<int>> dist(BOARD_SIZE, vector<int>(BOARD_SIZE, INF));\n        dist[startRow][startCol] = 0;\n        queue<pair<int, int>> q;\n        q.push({startRow, startCol});\n\n        while (!q.empty()) {\n            auto [currentRow, currentCol] = q.front();\n            q.pop();\n            for ( const auto& move : KNIGHT_MOVES ) \n            {\n                int newRow = currentRow + move[0];\n                int newCol = currentCol + move[1];\n                if ( newRow >= 0 && newRow < BOARD_SIZE && newCol >= 0 && newCol < BOARD_SIZE && dist[newRow][newCol] > dist[currentRow][currentCol] + 1 ) \n                {\n                    dist[newRow][newCol] = dist[currentRow][currentCol] + 1;\n                    q.push({newRow, newCol});\n                }\n            }\n        }\n        return dist;\n    }\n\n    // Recursive function to calculate the maximum moves considering both players\' optimal strategies\n    // TC & SC: O(N^2).\n    int calculateMaxMoves(int currentIndex, int turn, int mask, const vector<vector<int>>& positions) \n    {\n        if ( __builtin_popcount(mask) == positions.size() ) \n            return 0; // All pawns are captured\n\n        if ( dp[turn][currentIndex][mask] != -1 )\n            return dp[turn][currentIndex][mask];\n\n        int currentRow = positions[currentIndex][0];\n        int currentCol = positions[currentIndex][1];\n        int result = turn ? INF : -INF;\n\n        for ( int i=0; i<positions.size(); i++ ) \n        {\n            if ( !(mask & (1 << i)) )\n            {\n                int nextRow = positions[i][0];\n                int nextCol = positions[i][1];\n                int moveCost = minMoves[currentRow][currentCol][nextRow][nextCol];\n                if ( !turn )\n                    result = max(result, moveCost + calculateMaxMoves(i, 1 - turn, mask | (1 << i), positions));\n                else\n                    result = min(result, moveCost + calculateMaxMoves(i, 1 - turn, mask | (1 << i), positions));\n            }\n        }\n        return dp[turn][currentIndex][mask] = result;\n    }\n};\n```\n
['Dynamic Programming', 'C']