BFS + Bitmask DP | Optimal Solution | C++ Game Theory
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem involves a knight moving on a chessboard and trying to visit multiple posi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem involves a knight moving on a chessboard and trying to visit multiple positions with both players (Alice and Bob) taking turns. The goal is to calculate the maximum number of moves Alice can make, assuming both play optimally.\n\n### Key Intuition:\n1. **Knight\'s Movement:** The knight moves in an "L" shape, giving eight possible directions from any position. For each starting position, we compute the minimum number of moves required to reach every other position.\n   \n2. **State Representation:** The game is a turn-based strategy where Alice and Bob take turns. Alice tries to maximize her total moves, while Bob tries to minimize the score. This can be represented using dynamic programming (DP) with bitmasking to track which positions are visited and whose turn it is.\n\n3. **DP + Bitmasking:** Each state of the game can be represented by:\n   - `index`: the current position of the knight.\n   - `bitMask`: a bitmask representing the unvisited positions.\n   - `Alice`: a boolean indicating whose turn it is.\n   \n   Using this information, we recursively compute the optimal number of moves for both players. The bitmask allows us to efficiently track which positions have been visited.\n\n4. **Recursive Strategy:** Starting from Alice\u2019s turn, we try every possible position the knight can move to and recursively calculate the result for both Alice and Bob. The result is memoized to avoid recomputation, and the game ends when all positions are visited.\n\nThis approach ensures that both players make optimal moves, maximizing Alice\'s final score.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n### Stepwise Approach:\n\n1. **Define Directions for Knight\u2019s Movement:**\n   - The knight in chess moves in an "L" shape. There are 8 possible moves from any given position, represented by coordinate changes (\xB11, \xB12) or (\xB12, \xB11). \n   - Create a list of these directional movements.\n\n2. **BFS to Calculate Minimum Moves Between Positions:**\n   - For each position on the board (including the knight\'s starting position), use BFS (Breadth-First Search) to calculate the minimum number of moves required for the knight to reach every other position.\n   - Store the distances in a 2D matrix `minDist`, where `minDist[i][j]` represents the minimum number of moves from position `i` to position `j`.\n\n3. **Dynamic Programming with Bitmasking:**\n   - Use a 3D DP table `dp[index][bitMask][turn]` where:\n     - `index` represents the current position of the knight.\n     - `bitMask` is a bitmask that tracks which positions are still unvisited.\n     - `turn` is a boolean (`true` for Alice and `false` for Bob) indicating whose turn it is.\n   - Initialize all DP states to -1 (uncomputed).\n\n4. **Recursive DP Function:**\n   - Start from position 0 (knight\'s initial position) with all positions unvisited except the initial one. Set `bitMask = (1 << (n-1)) - 1` to represent the unvisited positions.\n   - On each move:\n     - If it\'s Alice\'s turn, she will choose the move that maximizes the total score.\n     - If it\'s Bob\'s turn, he will choose the move that minimizes the score.\n   - For each unvisited position, calculate the new state recursively by updating the bitmask and alternating the turn between Alice and Bob.\n   - The base case is when all positions have been visited (`bitMask == 0`), at which point the recursion stops.\n\n5. **Memoize Results:**\n   - Memoize the result of each state in the DP table to avoid recalculating the same state multiple times.\n\n6. **Return the Maximum Score:**\n   - Once all recursive calculations are done, return the maximum score that Alice can achieve from the starting state.\n\n### Final Solution:\n- Alice tries to maximize her score by making optimal moves, while Bob tries to minimize it.\n- The solution involves bitmasking to track visited positions and dynamic programming to handle turn-based optimal decision-making.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*2^n*n) == O(n^2*2^n) == O(2^n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(2^n)$$\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<pair<int,int>> dir = {{1,2}, {-1,2}, {1,-2}, {-1,-2}, {2,1}, {-2,1}, {2,-1}, {-2,-1}};\n    void BFS(int x, int y, vector<vector<int>>& positions, int index, vector<vector<int>>& minDist){\n        vector<vector<int>> v(50, vector<int>(50, -1)); // Visited matrix with distances\n        queue<pair<int, int>> q;\n        q.push({x, y});\n        v[x][y] = 0;\n\n        while(!q.empty()){\n            auto [currX, currY] = q.front();\n            q.pop();\n            for(auto& d : dir){\n                int newX = currX + d.first;\n                int newY = currY + d.second;\n                if(newX >= 0 && newX < 50 && newY >= 0 && newY < 50 && v[newX][newY] == -1){\n                    q.push({newX, newY});\n                    v[newX][newY] = v[currX][currY] + 1;\n                }\n            }\n        }\n        // Populate minDist with distances from (x, y) to all other positions\n        for(int i = 0; i < positions.size(); i++){\n            int x_bar = positions[i][0];\n            int y_bar = positions[i][1];\n            minDist[index][i] = v[x_bar][y_bar];\n        }\n    }\n\n    int solve(vector<vector<int>>& minDist, int index, int bitMask, bool Alice, int n, vector<vector<vector<int>>>& dp){\n        if(bitMask == 0)    return 0;\n        if(dp[index][bitMask][Alice] != -1) return dp[index][bitMask][Alice];\n        int res = (Alice == true) ? -1 : INT_MAX;\n        // Try every position\n        for(int i = 1; i < n; i++){\n            int moves = minDist[index][i];\n            if(bitMask & (1 << (i-1))){  // If the i-th position is unvisited\n                if(Alice){\n                    res = max(res, moves + solve(minDist, i, bitMask ^ (1 << (i-1)), false, n, dp));  // Alice\'s turn\n                } else {\n                    res = min(res, moves + solve(minDist, i, bitMask ^ (1 << (i-1)), true, n, dp));   // Bob\'s turn\n                }\n            }\n        }\n\n        return dp[index][bitMask][Alice] = res;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        int n = positions.size() + 1;\n        positions.insert(positions.begin(), {kx, ky});\n        vector<vector<int>> minDist(n, vector<int>(n, INT_MAX));\n        // Run BFS from each position to calculate pairwise distances\n        for(int index = 0; index < positions.size(); index++){\n            int x = positions[index][0];\n            int y = positions[index][1];\n            BFS(x, y, positions, index, minDist);\n        }\n        vector<vector<vector<int>>> dp(n, vector<vector<int>>(1 << (n-1), vector<int>(2, -1)));\n        bool Alice = true;\n        return solve(minDist, 0, (1 << (n-1)) - 1, Alice, n, dp);\n    }\n};\n\n```
['Dynamic Programming', 'Breadth-First Search', 'Matrix', 'Game Theory', 'Bitmask', 'C++']