BFS + Bitmask top-down DP | C++
Complexity\n- Time complexity: O(n^2*2^n)\n Add your time complexity here, e.g. O(n) \n\n# Code\ncpp []\nint dist[50][50][50][50];\nint ri[8] = {-1, 1, 2, 2, 1,
# Complexity\n- Time complexity: $$O(n^2*2^n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nint dist[50][50][50][50];\nint ri[8] = {-1, 1, 2, 2, 1, -1, -2, -2};\nint ci[8] = {2, 2, 1, -1, -2, -2, -1, 1};\n\nvoid bfs(int si, int ei){\n    queue<pair<pair<int, int>, int>>q;\n    q.push({{si, ei}, 0});\n    dist[si][ei][si][ei]=0;\n    while(!q.empty()){\n        int r=q.front().first.first;\n        int c=q.front().first.second;\n        int d=q.front().second;\n        q.pop();\n        for(int i=0;i<8;i++){\n            int nr=r+ri[i], nc=c+ci[i];\n            if(nr>=0 && nc>=0 && nr<50 && nc<50 && dist[si][ei][nr][nc]==-1){\n                dist[si][ei][nr][nc] = 1+d;\n                q.push({{nr, nc}, 1+d});\n            }\n        }\n    }\n    return;\n}\n\nvoid precomp(){\n    static bool fg=0;\n    if(fg)return;\n    memset(dist, -1, sizeof(dist));\n    for(int i=0;i<50;i++)\n    for(int j=0;j<50;j++)bfs(i, j);\n    fg=1;\n    return;\n}\n\nclass Solution {\npublic:\n\n    vector<vector<int>> dp;\n\n    int tdp(int curr, int msk, int turn, vector<vector<int>>&pos){\n        int n=pos.size();\n        if(msk==((1<<n)-1))return 0;\n        if(dp[curr][msk]!=-1)return dp[curr][msk];\n        int ans=0;\n        if(!turn){\n            ans=INT_MIN;\n            for(int i=0;i<n;i++){\n                if(msk&(1<<i))continue;\n                ans=max(ans, dist[pos[curr][0]][pos[curr][1]][pos[i][0]][pos[i][1]]+tdp(i, msk|(1<<i), !turn, pos));\n            }\n        }\n        else{\n            ans=INT_MAX;\n            for(int i=0;i<n;i++){\n                if(msk&(1<<i))continue;\n                ans=min(ans, dist[pos[curr][0]][pos[curr][1]][pos[i][0]][pos[i][1]]+tdp(i, msk|(1<<i), !turn, pos));\n            }\n        }\n        return dp[curr][msk]=ans;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        positions.push_back({kx, ky});\n        precomp();\n        int n=positions.size();\n        dp.resize(n, vector<int>(1 << n, -1));\n        return tdp(n-1, 1<<(n-1), 0, positions);\n    }\n};\n```
['Dynamic Programming', 'Breadth-First Search', 'C++']