Optimized BFS | Beats 100%| C++ | O(n*n*2^n)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nNote -> Tight test case
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Note ->** Tight test cases , Optimized BFS needed to avoid TLE. \nDon\'t search full grid. Break when all positions reached.\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 []\nint dis[50][50],vis[50][50],dx[8]={-2,-2,-1,1,2,2,1,-1},dy[8]={1,-1,-2,-2,-1,1,2,2};\nint dp[1<<16][16],n;\nqueue<vector<int> > q;\n\nint bfs(vector<int> z)\n{\n    while(!q.empty())\n    {\n        auto y=q.front();\n        for(int i=0;i<8;i++)\n        {\n            if(y[0]+dx[i]>=0 && y[0]+dx[i]<=49 && y[1]+dy[i]>=0 && y[1]+dy[i]<=49)\n            {\n                if(vis[y[0]][y[1]]+1<vis[y[0]+dx[i]][y[1]+dy[i]])\n                {\n                    vis[y[0]+dx[i]][y[1]+dy[i]]=vis[y[0]][y[1]]+1;\n                    q.push({y[0]+dx[i],y[1]+dy[i]});\n\n                    if(y[0]+dx[i] == z[0] && y[1]+dy[i] == z[1])\n                    return vis[y[0]+dx[i]][y[1]+dy[i]];\n                }\n            }\n        }\n        q.pop();\n    }\n    return vis[z[0]][z[1]];\n}\n\nint solve(int mask, int pos, vector<vector<int>>& positions)\n{\n    if(pos>=n || mask==(1<<n)-1)\n        return 0;\n    \n    if(dp[mask][pos]!=-1)\n        return dp[mask][pos];\n    \n    int x=__builtin_popcount(mask),ans,j;\n    if(x%2==0)\n    {\n        ans=0;\n        for(j=0;j<n;j++)\n        {\n            if(j!=pos && !(mask & (1<<j)))\n            {\n                ans=max(ans,dis[j][pos]+solve(mask|(1<<pos),j, positions));\n            }\n        }\n    }\n    else\n    {\n        ans=1e9;\n        for(j=0;j<n;j++)\n        {\n            if(j!=pos && !(mask & (1<<j)))\n            {\n                ans=min(ans,dis[j][pos]+solve(mask|(1<<pos),j, positions));\n            }\n        }\n    }\n    ans=(ans==1e9)?0:ans;\n    return dp[mask][pos]=ans;\n}\n\nclass Solution {\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        positions.push_back({kx,ky});\n        n=positions.size();\n        int i,j,k,l;\n        for(i=0;i<n;i++)\n        {\n            for(k=0;k<50;k++)\n            {\n                for(l=0;l<50;l++)\n                vis[k][l]=1e6;\n            }\n            vis[positions[i][0]][positions[i][1]]=0;\n\n            while(!q.empty())q.pop();\n            q.push(positions[i]);\n\n            for(j=i+1;j<n;j++)\n            {\n                if(vis[positions[j][0]][positions[j][1]]==1e6)\n                bfs(positions[j]);\n                dis[i][j]=dis[j][i]=vis[positions[j][0]][positions[j][1]];\n            }\n        }\n        memset(dp,-1,sizeof(dp));\n        return solve(0,n-1,positions);\n    }\n};\n```
['C++']