Easiest Code 100% faster than others using BFS and Dp
Code is just lenghty.\nFirst we calculated 3d vector that is shortest distance to reach point i, j from all points in positions (standard problem) and then just
Code is just lenghty.\nFirst we calculated 3d vector that is shortest distance to reach point i, j from all points in positions (standard problem) and then just used dp and seeing whose turn it is. If it is Alice we have to maximize it otherwise minimize it. \nLastly just used hashing using bits to memoise dp.\n\n# Code\n```cpp []\nclass Solution {\n    const vector<pair<int, int>> directions = {\n        {2, 1}, {2, -1}, {-2, 1}, {-2, -1},\n        {1, 2}, {1, -2}, {-1, 2}, {-1, -2}\n    };\n\n    bool isValid(int x, int y) {\n        return x >= 0 && x < 50 && y >= 0 && y < 50;\n    }\n\n    vector<vector<int>> knightMinSteps(int startX, int startY) {\n        vector<vector<int>> minSteps(50, vector<int>(50, INT_MAX)); \n        queue<pair<int, int>> q;\n\n        minSteps[startX][startY] = 0;\n        q.push({startX, startY});\n\n        while (!q.empty()) {\n            int x = q.front().first;\n            int y = q.front().second;\n            q.pop();\n\n            for (const auto& dir : directions) {\n                int newX = x + dir.first;\n                int newY = y + dir.second;\n\n                if (isValid(newX, newY) && minSteps[newX][newY] == INT_MAX) {\n                    minSteps[newX][newY] = minSteps[x][y] + 1;\n                    q.push({newX, newY});\n                }\n            }\n        }\n\n        return minSteps;\n    }\n\n\n    vector<vector<vector<int>>> v;\n\n    int dp[100000][16][2];\n    int solve(int hash, int last, int f, int n, vector<vector<int>>& positions){\n        if(hash == (1 << n) - 1) return 0;\n\n        if(dp[hash][last][f] != -1) return dp[hash][last][f];\n\n        int ans = 0;\n\n        if(f){\n            int cnt = 0;\n            for(int i = 0; i < n; i++){\n                if((hash >> i) & 1) continue;\n                cnt = max(cnt, v[last][positions[i][0]][positions[i][1]] + solve(hash | (1 << i), i, 0, n, positions));\n            }\n            ans = cnt;\n        }\n        else{\n            int cnt = INT_MAX;\n            for(int i = 0; i < n; i++){\n                if((hash >> i) & 1) continue;\n                cnt = min(cnt, v[last][positions[i][0]][positions[i][1]] + solve(hash | (1 << i), i, 1, n, positions));\n            }\n            ans = cnt;\n        }\n\n        return dp[hash][last][f] = ans;\n    }\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        int n = positions.size();\n        positions.push_back({kx, ky});\n\n        // calculated shortest to every point i, j from every point in positions.\n        v.assign(n+1, vector<vector<int>>(50, vector<int>(50, INT_MAX)));\n\n        for (int k = 0; k <= n; k++) {\n            int p = positions[k][0], q = positions[k][1];\n            vector<vector<int>> minSteps = knightMinSteps(p, q);\n            for (int i = 0; i < 50; ++i) {\n                for (int j = 0; j < 50; ++j) {\n                    v[k][i][j] = minSteps[i][j];\n                }\n            }\n        }\n        memset(dp, -1, sizeof(dp));\n        return solve((1 << n), n, 1, n+1, positions);\n    }\n};\n```
['Dynamic Programming', 'Breadth-First Search', 'C++']