DP + Bitmask + BFS || Beats 100% || C++
\n# Complexity\n- Time complexity:O(n^2 * 2^n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n * 2^n)\n Add your space complexity here, e.
\n# Complexity\n- Time complexity:$$O(n^2 * 2^n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n * 2^n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    struct cell {\n        int x, y;\n        int dis;\n        cell() {}\n        cell(int x, int y, int dis)\n            : x(x)\n            , y(y)\n            , dis(dis)\n        {\n        }\n    };\n\n    bool isInside(int x, int y, int N)\n    {\n        if (x >= 0 && x < N && y >= 0 && y < N)\n            return true;\n        return false;\n    }\n\n    int minStepToReachTarget(vector<int>& knightPos, vector<int>& targetPos,\n                             int N)\n    {\n        int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };\n        int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };\n\n        queue<cell> q;\n\n        q.push(cell(knightPos[0], knightPos[1], 0));\n\n        cell t;\n        int x, y;\n        bool visit[N + 1][N + 1];\n\n        memset(visit, false, sizeof(visit));\n\n        visit[knightPos[0]][knightPos[1]] = true;\n\n        while (!q.empty()) {\n            t = q.front();\n            q.pop();\n\n            if (t.x == targetPos[0] && t.y == targetPos[1])\n                return t.dis;\n\n            for (int i = 0; i < 8; i++) {\n                x = t.x + dx[i];\n                y = t.y + dy[i];\n\n                if (isInside(x, y, N) && !visit[x][y]) {\n                    visit[x][y] = true;\n                    q.push(cell(x, y, t.dis + 1));\n                }\n            }\n        }\n\n        return -1;\n    }\n    int dp[16][2][1 << 15];\n    int solve(int knight, int turn, int mask, vector<vector<int>>& dis, int n){\n        if(mask == 0) return 0;\n        if(dp[knight][turn][mask] != -1) return dp[knight][turn][mask];\n        int maxi = turn ? 1e9 : -1e9;\n        for(int i=0; i<n; i++){\n            if(mask & (1 << i)){\n                if(turn){\n                    maxi = min(maxi, dis[knight][i] + solve(i, !turn, mask ^ (1 << i), dis, n));\n                }else{\n                    maxi = max(maxi, dis[knight][i] + solve(i, !turn, mask ^ (1 << i), dis, n));\n                }\n            }\n        }\n        return dp[knight][turn][mask] =  maxi;\n    }\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        int n = positions.size();\n        positions.push_back({kx, ky});\n        vector<vector<int>> dis(n+1, vector<int>(n+1));\n        for(int i=0; i<=n; i++){\n            for(int j=i+1; j<=n; j++){\n                int val = minStepToReachTarget(positions[i], positions[j], 50);\n                dis[i][j] = val;\n                dis[j][i] = val;\n            }\n        }\n        memset(dp, -1, sizeof dp);\n        return solve(n, 0, (1 << n) - 1, dis, n);\n    }\n};\n```
['C++']