Video Explanation (Starting with a simpler version and then building on top)
Explanation\n\nClick here for the video\n\n# Code\ncpp []\n#define pii pair<int, int>\n#define F first\n#define S second\n\nint moves[50][50][50][50];\nint dp[2
# Explanation\n\n[Click here for the video](https://youtu.be/jTYOuiKwhxo)\n\n# Code\n```cpp []\n#define pii pair<int, int>\n#define F first\n#define S second\n\nint moves[50][50][50][50];\nint dp[2][16][1 << 16];\n\nvector<pii> knight_diff = {\n    {-2, 1}, {-2, -1}, {2, 1}, {2, -1}, \n    {-1, 2}, {-1, -2}, {1, 2}, {1, -2}\n};\n\nbool already_computed = false;\n\nclass Solution {\n    \n    void Expand (int x, int y) {\n        vector<vector<bool>> visited(50, vector<bool>(50, false));\n        queue<pii> q;\n        \n        moves[x][y][x][y] = 0;\n        q.push({x, y});\n        visited[x][y] = true;\n        \n        while (!q.empty()) {\n            pii s = q.front();\n            q.pop();\n            \n            for (auto i : knight_diff) {\n                int nxt_x = i.F + s.F;\n                int nxt_y = i.S + s.S;\n                \n                bool is_valid = (nxt_x >= 0 && nxt_x < 50) && (nxt_y >= 0 && nxt_y < 50);\n                if (!is_valid || visited[nxt_x][nxt_y]) continue;\n                \n                moves[x][y][nxt_x][nxt_y] = 1 + moves[x][y][s.F][s.S];\n                q.push({nxt_x, nxt_y});\n                visited[nxt_x][nxt_y] = true;\n            }\n        }\n    }\n    \n    void CalculateAll () {\n        if (already_computed) return;\n        \n        already_computed = true;\n        for (int kx = 0; kx < 50; kx ++) {\n            for (int ky = 0; ky < 50; ky ++) {\n                Expand (kx, ky);\n            }\n        }\n    }\n    \n    vector<vector<int>> pawns;\n    int pawns_cnt;\n    \n    int Moves (int alice_turn, int last_taken, int taken_mask) {\n        if (taken_mask == ((1 << pawns_cnt)-1)) return 0;\n        \n        int &ans = dp[alice_turn][last_taken][taken_mask];\n        if (ans != -1) return ans;\n        \n        int x = pawns[last_taken][0], y = pawns[last_taken][1];\n        ans = alice_turn? 0 : INT_MAX;\n        \n        for (int i = 0; i < pawns_cnt; i ++) {\n            if ((1 << i) & taken_mask) continue;\n            \n            int nxt_x = pawns[i][0], nxt_y = pawns[i][1];\n            int steps = Moves(alice_turn^1, i, taken_mask|(1 << i)) + moves[x][y][nxt_x][nxt_y];\n            \n            if (alice_turn) ans = max (ans, steps);\n            else ans = min (ans, steps);\n        }\n        return ans;\n    }\n    \npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        CalculateAll();\n        memset(dp, -1, sizeof(dp));\n        \n        pawns = positions;\n        pawns.push_back({kx, ky});\n        pawns_cnt = pawns.size();\n        \n        return Moves (1, pawns_cnt-1, (1 << (pawns_cnt-1)));\n    }\n};\n```
['C++']