EASY TO UNDERSTAND CODE | 80 Lines | DP + BFS Optimized
Approach\nDP + PreComputation using BFS\n Describe your approach to solving the problem. \n\n# Complexity\n- Time complexity: O(2^n * n) {n=length of pos}\n Add
# Approach\nDP + PreComputation using BFS\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(2^n * n) {n=length of pos}\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(2^n + 2*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<pair<int,int>> moves = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};\n\n    bool isValid(int x, int y){\n        if(x<0 || y<0 || x>49 || y>49){return 0;}\n        return 1;\n    }\n\n    vector<vector<int>> dist; //dist[i][j] = ct of moves to move from pos[i] to pos[j];\n\n    int bfs(int a, int b, int c, int d){\n        vector<vector<bool>> vis(50, vector<bool>(50, 0));\n\n        queue<pair<int,int>> q;\n        q.push({a,b});\n        vis[a][b] = 1;\n        int lvl = 0;\n\n        while(!q.empty()){\n            int k = q.size();\n            while(k--){\n                int x = q.front().first, y = q.front().second;\n                q.pop();\n\n                if(x==c && y==d){return lvl;}\n\n                for(auto &[xx, yy] : moves){\n                    int newX = x + xx, newY = y + yy;\n                    if(isValid(newX, newY) && !vis[newX][newY]){\n                        vis[newX][newY] = 1;\n                        q.push({newX, newY});\n                    }\n                }\n            }\n            lvl++;\n        }\n\n        return -1;\n    }\n    \n\n    int dp[16][65536][2];\n    int visAll;\n\n    int solve(int curr, int mask, bool isAlice, vector<vector<int>>&pos){\n        if(mask==visAll){return 0;}\n        if(dp[curr][mask][isAlice]!=-1){return dp[curr][mask][isAlice];}\n\n        int best = 0;\n        if(!isAlice){best = INT_MAX;}\n\n        for(int i=0; i<pos.size(); i++){\n            if((mask&(1<<i))==0){  // not vis;\n                int tmp = dist[curr][i] + solve(i, mask|(1<<i), !isAlice, pos);\n                if(isAlice){\n                    best = max(best, tmp);\n                }\n                else{\n                    best = min(best, tmp);\n                }\n            }\n        }\n\n        return dp[curr][mask][isAlice] = best;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions){\n        positions.push_back({kx, ky});\n        int n = positions.size();\n        visAll = (1<<n) - 1;\n\n        dist.resize(n, vector<int>(n, 0));\n\n        for(int i=0; i<n; i++){\n            int a = positions[i][0], b = positions[i][1];\n\n            for(int j=i+1; j<n; j++){\n                int c = positions[j][0], d = positions[j][1];\n                int ctMoves = bfs(a, b, c, d);\n                dist[i][j] = ctMoves;\n                dist[j][i] = ctMoves;\n            }\n        }\n\n        memset(dp, -1, sizeof(dp));\n\n        return solve(n-1, 1<<(n-1), 1, positions);\n        \n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Breadth-First Search', 'Bitmask', 'C++']