keep coding :)
Intuition\noptimization is toughest part of this problem.\n\n# Approach\n\nI precomputed the moves which it take from one pawn position to another by breadth fi
# Intuition\noptimization is toughest part of this problem.\n\n# Approach\n\nI precomputed the moves which it take from one pawn position to another by breadth first search (because dfs  is not optimal) and then i appliead dp in which one parameter is mask(keep track of which pawn position captured) and one parameter is turn and that clone parameter is index no in postion array for kx,ky the clone is n (size of position array).\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\ni had solved this problem in 6 hours so keep optimizing it, you can also solve this problem . \n# Code\n```cpp []\n\nclass Solution {\npublic:\n    bool check(int kx, int ky) {\n        return kx >= 0 && kx < 50 && ky >= 0 && ky < 50;\n    }\n\n    int bfs(int kx, int ky, int fx, int fy) {\n        vector<vector<int>> moves = {\n            {2, 1}, {2, -1}, {-2, 1}, {-2, -1},\n            {1, 2}, {1, -2}, {-1, 2}, {-1, -2}\n        };\n\n        queue<pair<int, int>> q;\n        q.push({kx, ky});\n        vector<vector<int>> dist(50, vector<int>(50, INT_MAX));\n        dist[kx][ky] = 0;\n\n        while (!q.empty()) {\n            auto [x, y] = q.front();\n            q.pop();\n\n            if (x == fx && y == fy) {\n                return dist[x][y];\n            }\n\n            for (auto& move : moves) {\n                int nx = x + move[0];\n                int ny = y + move[1];\n\n                if (check(nx, ny) && dist[nx][ny] == INT_MAX) {\n                    dist[nx][ny] = dist[x][y] + 1;\n                    q.push({nx, ny});\n                }\n            }\n        }\n\n        return INT_MAX;  \n    }\n\n    int help(int kx, int ky, vector<vector<int>>& positions,  vector<vector<vector<int>>> & dp, int chance, int mask,int clone,vector<vector<int>>&knight) {\n        int n = positions.size();\n        if (mask == (1 << n) - 1) { \n            return 0;\n        }\n        if (dp[mask][chance][clone] != -1) {\n            return dp[mask][chance][clone];\n        }\n\n        int bestMoves = (chance == 0) ? INT_MIN : INT_MAX;\n\n        for (int i = 0; i < n; i++) {\n            if ((mask & (1 << i)) == 0) {  \n                int moveCount = knight[clone][i];\n                int newMask = mask | (1 << i);\n                if (chance == 0) {  \n                    bestMoves = max(bestMoves, moveCount + help(positions[i][0], positions[i][1], positions, dp, 1, newMask,i,knight));\n                } else {  \n                    bestMoves = min(bestMoves, moveCount + help(positions[i][0], positions[i][1], positions, dp, 0, newMask,i,knight));\n                }\n            }\n        }\n\n        return dp[mask][chance][clone] = bestMoves;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        int n = positions.size();\n  vector<vector<int>>temp=positions;\n  temp.push_back({kx,ky});\n        vector<vector<int>>knight(n+1,vector<int>(n+1,0));\n        for(int i=0;i<=n;i++){\n            for(int j=0;j<=n;j++){\n                knight[i][j]=bfs(temp[i][0],temp[i][1],temp[j][0],temp[j][1]);\n            }\n        }\n\n      vector<vector<vector<int>>>dp(1<<n,vector<vector<int>>(2,vector<int>(n+1,-1)));\n        return help(kx, ky, positions, dp, 0, 0,n,knight); \n    }\n};\n\n```
['Dynamic Programming', 'Breadth-First Search', 'Game Theory', 'Bitmask', 'C++']