BFS + Bitmask DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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 []\n    const int N = 50;\n    vector<vector<int>> dis[51][51];\n    bool flag = false;\n    int dir_x[8] = {-2,-1,1,2,2,1,-1,-2};\n    int dir_y[8] = {1,2,2,1,-1,-2,-2,-1};\n\n\n    int dp[16][2][1<<16];\n\n    bool check(int x,int y)\n    {\n        return (x < 50 && x >= 0 && y < 50 && y >= 0);\n    }\n\n\n    vector<vector<int>> bfs(int x,int y)\n    {\n        vector<vector<int>> cost(N,vector<int>(N,1e9));\n\n        cost[x][y] = 0;\n\n        queue<pair<int,int>> q;\n        q.push({x,y});\n\n        while(!q.empty())\n        {\n            int r = q.front().first;\n            int c = q.front().second;\n            q.pop();\n\n            for(int i = 0; i < 8; i++)\n            {\n                int n_row = r + dir_x[i];\n                int n_col = c + dir_y[i];\n\n                if(check(n_row,n_col) && cost[n_row][n_col] > cost[r][c] + 1)\n                {\n                    cost[n_row][n_col] = cost[r][c] + 1;\n\n                    q.push({n_row,n_col});\n                }\n            }\n        }\n\n        return cost;\n    }\n\n\nclass Solution {\npublic:\n  \n    void preprocess()\n    {\n        if(flag) return;\n\n        flag = true;\n\n        for(int i = 0; i < 50; i++)\n        {\n            for(int j = 0; j < 50; j++)\n            {\n                vector<vector<int>> dist = bfs(i,j);\n                dis[i][j] = dist;\n            }\n        }\n\n    }\n\n    int rec(int ind,int turn,int mask,vector<vector<int>>& pos)\n    {\n        if(ind == pos.size())\n        return 0;\n\n        if(mask == ((1 << (pos.size()))-1))\n        return 0;\n        // // base\n    //     if(__builtin_popcount(mask) == (int)pos.size()) {\n    //         return 0;\n    // }\n\n        if(dp[ind][turn][mask] != -1) return dp[ind][turn][mask];\n        // trans\n\n        int ans = (turn == 0) ? -1e9  : 1e9;\n        int src_x = pos[ind][0];\n        int src_y = pos[ind][1];\n        for(int i = 0; i < pos.size(); i++)\n        {\n            int dest_x = pos[i][0];\n            int dest_y = pos[i][1];\n            if(!(mask & (1<<i)))\n            {\n                if(turn == 0) // alice\n                {\n                    ans = max(ans,dis[src_x][src_y][dest_x][dest_y] + rec(i,1-turn,(mask|(1<<i)),pos));\n                }\n                else // bob\n                {\n                    ans = min(ans,dis[src_x][src_y][dest_x][dest_y] + rec(i,1-turn,(mask|(1<<i)),pos));\n                }\n            }\n        }\n\n        return dp[ind][turn][mask] = ans;\n    }\n    \n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        preprocess();\n        vector<vector<int>> pos;\n        pos.push_back({kx,ky});\n        for(auto it : positions)\n        pos.push_back({it[0],it[1]});\n\n        for(int i = 0; i < 16; i++)\n        {\n            for(int m = 0; m < (1<<16); m++)\n            {\n                dp[i][0][m] = -1;\n                dp[i][1][m] = -1;\n            }\n        }\n\n        return rec(0,0,1,pos);\n\n    }\n};\n```
['Dynamic Programming', 'Graph', 'Bitmask', 'C++']