DP + Bitmask + BFS find Shortest Path + Time Complexity Analysis || Beat 100%
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:\nO( N*(50*50) ) + O( N * (N * 2^N) )\n(BFS)          + (Each state change time * All state)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    #define ll long long\n    const ll INF = 1e18;\n    const vector<pair<int, int>> dir = { {-2, -1}, {-2, 1}, {2, -1}, {2, 1},\n                                        {-1, -2}, {-1, 2}, {1, -2}, {1, 2} };\n    int n, base;\n    ll dpBob[1<<15][16] = {0};\n    ll dpAlice[1<<15][16] = {0};\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) \n    {\n        n = positions.size();\n        base = (1<<n)-1;\n        vector<vector<ll>> dis(n, vector<ll>(n));\n        // find distance between each pawn\n        for (int i = 0; i < n; i++)\n        {\n            dis[i] = findDis(positions[i][0], positions[i][1], positions);\n        }\n        // find distance between original position of knight and all the pawns\n        vector<ll> firstK = findDis(kx, ky, positions);\n\n        ll res = 0;\n        // Alice first move\n        for (int i = 0; i < n; i++)\n        {\n            res = max(res, firstK[i] + turnBob(i, 1<<i, dis));\n        }\n        return (int)res;\n    }\nprivate:\n    vector<ll> findDis(int sx, int sy, vector<vector<int>>& positions)\n    {\n        vector<vector<ll>> disGrid(50, vector<ll>(50, INF));\n        vector<ll> disS(n, 0);\n        queue<pair<int,int>> q;\n        disGrid[sx][sy] = 0;\n        q.push({sx, sy});\n        while (!q.empty())\n        {\n            int x = q.front().first, y = q.front().second;\n            q.pop();\n            for (auto &move:dir)\n            {\n                int nx = x + move.first, ny = y + move.second;\n                if (0<=nx && nx<50 && 0<=ny && ny<50 && disGrid[nx][ny] > disGrid[x][y] + 1)\n                {\n                    disGrid[nx][ny] = disGrid[x][y] + 1;\n                    q.push({nx, ny});\n                }\n            }\n        }\n        for (int i = 0; i < n; i++)\n            disS[i] = disGrid[positions[i][0]][positions[i][1]];\n        return disS;\n    }\n\n    ll turnBob(int i, int mask, vector<vector<ll>> &dis)\n    {\n        if (mask==base) return 0;\n        // dp\n        if (dpBob[mask][i] != 0) return dpBob[mask][i];\n        ll ans = INF;\n        for (int j = 0; j <n; j++)\n        {\n            if ((mask&(1<<j)) == 0)\n            {\n                // Bod try: move from pawn i to pawn j, and then Alice\'s turn\n                ans = min(ans, turnAlice(j, mask|(1<<j), dis) + dis[i][j] );\n            }\n        }\n        return dpBob[mask][i] = ans;\n    }\n\n    ll turnAlice(int i, int mask, vector<vector<ll>> &dis)\n    {\n        if (mask==base) return 0;\n        // dp\n        if (dpAlice[mask][i] != 0) return dpAlice[mask][i];\n        ll ans = -INF;\n        for (int j = 0; j <n; j++)\n        {\n            if ((mask&(1<<j)) == 0)\n            {\n                // Alice try: move from pawn i to pawn j, and then Bob\'s turn\n                ans = max(ans, turnBob(j, mask|(1<<j), dis) + dis[i][j] );\n            }\n        }\n        return dpAlice[mask][i] = ans;\n    }\n};\n```
['C++']