Bitmask DP
\n\n# Code\ncpp []\nclass Solution {\npublic:\n    int xf;\n    int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};\n    int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};\n    in
\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int xf;\n    int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};\n    int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};\n    int dp[32769][2][16];\n    void getCost(int pos, vector<vector<int>> &arr, map< pair<int, int>, int> &m, vector< vector<int> > &dist)\n{\n    int x = arr[pos][0];\n    int y = arr[pos][1];\n \n    vector< vector<int> > vis(51, vector<int>(51, 0)); // visited array of size 51*51. \n    \n    int n = arr.size();\n    queue< tuple<int, int, int> > q;\n    q.push({0, x, y}); \n    tuple<int, int, int> tp;\n    int total = 0;\n\n    while(q.size() > 0 && total < n)\n    {\n        tuple<int, int, int> t = q.front(); \n        q.pop();\n        int cost = get<0>(t);\n        x = get<1>(t);\n        y = get<2>(t);\n        if(vis[x][y] == 1)\n            continue;\n        vis[x][y] = 1;\n        \n        if(m.find({x ,y}) != m.end())\n        {\n            ++total;\n            int p1 = pos;\n            int p2 = m[{x, y}];\n            dist[p1][p2] = cost;\n        }\n        \n        for(int i=0; i<8; ++i)\n        {\n            int nx = x + dx[i];\n            int ny = y + dy[i];\n            \n            if(nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && vis[nx][ny] == 0)\n            {\n                q.push({cost+1, nx, ny});\n            }\n        }\n    }\n}\n\n    long long helper(int mask, int turn, int pos, vector<vector<int>>& arr, vector< vector<int> > &g) {\n        if(mask == xf) {\n            return 0;\n        }\n        if(pos >= 0 && dp[mask][turn][pos] != -1) {\n            return dp[mask][turn][pos];\n        }\n        long long ans;\n        if(turn == 0) {\n            ans = 0;\n            for(int j = 1; j < arr.size(); j++) {\n                int r = j - 1;\n                if(((1 << r) & mask) == 0) {\n                    int newMask = mask | (1 << r);\n                    ans = max(ans, g[pos][j] + helper(newMask, 1, j, arr, g));\n                }\n            }\n        }\n        else {\n            ans = INT_MAX;\n            for(int j = 1; j < arr.size(); j++) {\n                int r = j - 1;\n                if(((1 << r) & mask) == 0) {\n                    int newMask = mask | (1 << r);\n                    ans = min(ans, g[pos][j] + helper(newMask, 0, j, arr, g));\n                }\n            }\n        }\n        return dp[mask][turn][pos] = ans;\n    }\n    int maxMoves(int kx, int ky, vector<vector<int>>& pos) {\n        memset(dp, -1, sizeof(dp));\n        vector<vector<int>> arr;\n        arr.push_back({kx, ky});\n        map< pair<int, int>, int> m;\n        m[{kx, ky}] = 0;\n        for(int i=0; i<pos.size(); ++i)\n        {\n            arr.push_back({pos[i][0], pos[i][1]}); \n            m[{pos[i][0], pos[i][1]}] = i+1; \n        }\n        int n = arr.size();\n        vector< vector<int> > dist(n+1, vector<int>(n + 1, 0)); \n        for(int i = 0; i < arr.size(); ++i)\n        {\n            getCost(i, arr, m, dist);\n        }\n        n = n-1;\n        xf = pow(2, n)-1;\n        return helper(0, 0, 0, arr, dist);\n    }\n};\n```
['C++']