Beats 100% || Dp with Bitmask || BFS ||
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<vector<int>> directions = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},\n                                      {-1,2},{-1,-2}};\n\n    void bfs(int x, int y, vector<vector<int>>& pos, vector<vector<int>>& minDist, int index) {\n        vector<vector<int>> t(50, vector<int>(50, -1));\n        queue<pair<int, int>> qq;\n        qq.push({x, y});\n        t[x][y] = 0;\n\n        while (!qq.empty()) {\n            auto [curx, cury] = qq.front();\n            qq.pop();\n\n            for (auto& dir : directions) {\n                int nr = curx + dir[0];\n                int nc = cury + dir[1];\n                if (nr >= 0 && nr < 50 && nc >= 0 && nc < 50 && t[nr][nc] == -1) {\n                    t[nr][nc] = t[curx][cury] + 1;\n                    qq.push({nr, nc});\n                }\n            }\n        }\n\n        for (int i = 0; i < pos.size(); i++) {\n            int xx = pos[i][0];\n            int yy = pos[i][1];\n            minDist[index][i] = t[xx][yy];\n        }\n    }\n\n    int solve(vector<vector<int>>& minDist, int idx, int mask, int n, bool A, int dp[51][1<<15]) {\n        if (mask == 0) return 0;\n        if (dp[idx][mask]!= -1) return dp[idx][mask];\n\n        int res = (A ? -1 : 1e9);\n        for (int i = 1; i < n; i++) {\n            if (mask & (1 << (i - 1))) {\n                int moves = minDist[idx][i];\n                if (A) {\n                    res = max(res, moves + solve(minDist, i, \n                    mask ^ (1 << (i - 1)), n, !A, dp));\n                } else {\n                    res = min(res, moves + \n                    solve(minDist, i, mask ^ (1 << (i - 1)), n, !A, dp));\n                }\n            }\n        }\n        dp[idx][mask] = res;\n        return res;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        int n = positions.size();\n        vector<vector<int>> pos;\n        pos.push_back({kx, ky});\n        for (auto &it : positions) {\n            pos.push_back({it[0], it[1]});\n        }\n\n        vector<vector<int>> minDist(n + 1, vector<int>(n + 1, 0));\n        for (int i = 0; i < pos.size(); i++) {\n            int x = pos[i][0];\n            int y = pos[i][1];\n            bfs(x, y, pos, minDist, i);\n        }\n\nint dp[51][1<<15];\nmemset(dp,-1,sizeof(dp));\n        bool alice = true;\n\n        return solve(minDist, 0, (1 << n) - 1, pos.size(), alice,dp);\n    }\n};\n\n```
['C++']