Short Code BFS | Precompute | Bitmask Dp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\n# Approach\n Describe your approach to solving the problem. \n1. Solving using stat
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Solving using states of current position of knight : prev\nand number of pawns captured using bitmask : mask\n2. storing the distance between all pairs of pawns and inititial position of knight using a bfs \n3. applying dp to memoize\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    int dp[16][1 << 15][2];\n    int dr[8] = {-2, -1, 1, 2, 2, 1, -1, -2};\n    int dc[8] = {1, 2, 2, 1, -1, -2, -2, -1};\n    int dist[16][16];\n\n    void bfs(int id, int sr, int sc, int e_id, int er, int ec) {\n        vector<vector<int>> vis(50, vector<int>(50, 0));\n        vis[sr][sc] = 1;\n        queue<vector<int>> q;\n        q.push({0, sr, sc});\n        while(!q.empty()) {\n            auto it = q.front(); q.pop();\n            int curr = it[0], r = it[1], c = it[2];\n            if(r == er && c == ec) { dist[id][e_id] = dist[e_id][id] = curr; return; }\n            for(int i = 0; i < 8; i++) {\n                int nr = r + dr[i];\n                int nc = c + dc[i];\n                if(nr >= 0 && nr < 50 && nc >= 0 && nc < 50) {\n                    if(!vis[nr][nc]) {\n                        vis[nr][nc] = 1;\n                        int val = curr + 1;\n                        q.push({val, nr, nc});\n                    }\n                }\n            }\n        }\n    }\n\n    int solve(int prev, int mask, int ch, vector<vector<int>>& pos) {\n        int n = pos.size();\n        // ended at prev \n        if(mask == ( (1 << n) - 1) ) return 0;\n        if(dp[prev][mask][ch] != -1) return dp[prev][mask][ch];\n        int a = 0;\n        if(!ch) a = 1e9;\n        for(int i = 0; i < n; i++) {\n            if(mask & ( 1 << i)) continue;\n            int x = pos[i][0], y = pos[i][1];\n            int val = solve(i + 1, (mask | (1 << i)), !ch, pos)  + dist[prev][i + 1];\n            if(ch) a = max(a, val);\n            else a = min(a, val);\n        }\n        return dp[prev][mask][ch] = a;\n    }\n    int maxMoves(int kx, int ky, vector<vector<int>>& pos) {\n        int n = pos.size();\n        memset(dp, -1, sizeof(dp));\n\n        for(int i = 0; i < n; i++) bfs(0, kx, ky, i + 1, pos[i][0], pos[i][1]);\n        for(int i = 0; i < n; i++) {\n            int x = pos[i][0], y = pos[i][1];\n            for(int j = i + 1; j < n; j++) {\n                int x2 = pos[j][0], y2 = pos[j][1];\n                bfs(i + 1, x, y, j + 1, x2, y2);\n            }\n        }\n        return solve(0, 0, 1, pos);\n    }\n};\n```
['C++']