Why BFS, DP, Bitmask ?
Let\'s try to understand why BFS, Bitmask and DP come into picture. \nBefore going through the solution be sure to get full clarity on what the questionis askin
Let\'s try to understand why BFS, Bitmask and DP come into picture. \nBefore going through the solution be sure to get full clarity on what the questionis asking for. Cause initially I did this mistake of interpreting the question wrong. \n\n# Intuition\n* Chess board, Knight & No of moves, all point out to graph being involved, and BFS will be needed. \n* 2 players are playing, and both can make optimal decisions as per the constraint, which point out to some form of DP. \n* There can be any options at a given instant, like which pawn to pick up, which makes bit-mask DP a possiblity, and the range of no of position <15 confirm this.\n* Knight will alway end at a pwn position. It can not end at any randome position. \n\n# Approach\nBreaking down the approach:\n\n* The dp can be formulated in such a manner, if knight is at a position p3(pawn no 3 position), it will have the choice of all remain pawn to choose from. So for a unique we need to know where he knight is, if its alices turn and pwns chosen untill now. \ndp(pawnIdx, isAlice, mask) -> max possible moves such that knight is at pawnPos, it is Alice\'s turn and no of selected pawns untill now stored in mask. \n* There will be **two transitions**, one for alice and one for bob. Alice is concerned with maximising moves, so she chooses the pawn which is farthest, and Bob chooses the pawn which is nearest.\n_\ndp(pawnIdx, isAlice, mask) -> dp(i, !isAlice, mask`) + [no of moves]\n_\nKeep in mind, when alice is playing we are interested in maximising and when bob is palying we are interested in minimising. \n* We pre calculate distance of all nodes from all pawn and from the knight, so that we can get dist [ curCell -> nextPawn] in O(1).\n* **We need to start with knight as our starting position, and my DP, I do not consider knight\'s starting position when modifying mask. This makes the implementation quiet clean.** \n\n# Complexity\n- Time complexity:\nBFS + DP, where,\nBFS -> no of bfs * O(v+e) = 16*(2500 * (2500 * 8)) = 360000\nDP -> states * transitions = (15 * 2 * 1<<15) * 2 ~ 2000000\n\n- Space complexity:\nThis will be dist[] array + dp[] array.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int nPawn, n;\n    int dist[16][50][50];\n    int dp[16][2][65000];\n    vector<vector<int>> pawnPos;\n\n    int dx[8] = {-1,-2,-2,-1,1,2,2,1};\n    int dy[8] = {-2,-1,1,2,2,1,-1,-2};\n\n    bool check(int x,int y){\n        if(x<0||y<0||x>=n||y>=n){\n            return false;\n        }\n        return true;\n    }\n    \n    void bfsFromPawn(int pawnIdx){\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                dist[pawnIdx][i][j]=1e9;\n            }\n        }\n        dist[pawnIdx][pawnPos[pawnIdx][0]][pawnPos[pawnIdx][1]]=0;\n        queue<pair<int,int>> q;\n        q.push({pawnPos[pawnIdx][0], pawnPos[pawnIdx][1]});\n        while(!q.empty()){\n            pair<int,int> cur = q.front();\n            q.pop();\n            int curDist = dist[pawnIdx][cur.first][cur.second];\n            for(int k=0;k<8;k++){\n                int nx = cur.first+dx[k];\n                int ny = cur.second + dy[k];\n                if(!check(nx, ny))   continue;\n                if(dist[pawnIdx][nx][ny]>curDist+1){\n                    dist[pawnIdx][nx][ny]=curDist+1;\n                    q.push({nx,ny});\n                }\n            }\n        }\n        return;\n    }\n\n    int rec(int pawnIdx, int isAlice, int mask){\n        if(mask==((1<<nPawn)-1)){\n            return 0;\n        }\n\n        if(dp[pawnIdx][isAlice][mask]!=-1){\n            return dp[pawnIdx][isAlice][mask];\n        }\n\n        int ans = (isAlice)?-1e9:1e9;\n\n        for(int i=0;i<nPawn;i++){\n            if((1<<i)&mask) continue;\n            if(isAlice){\n                ans = max(ans, rec(i,!isAlice, (mask|(1<<i))) + dist[pawnIdx][pawnPos[i][0]][pawnPos[i][1]] );\n            }else{\n                ans = min(ans, rec(i,!isAlice, (mask|(1<<i))) + dist[pawnIdx][pawnPos[i][0]][pawnPos[i][1]] );\n            }\n        }\n\n        return dp[pawnIdx][isAlice][mask]=ans;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        memset(dp,-1,sizeof(dp));\n        pawnPos = positions;\n        nPawn = positions.size();\n        n=50;\n        pawnPos.push_back({kx,ky});\n        for(int i=0;i<=nPawn;i++){\n            bfsFromPawn(i);\n        }\n        return rec(nPawn, 1, 0);\n    }\n};\n```
['Dynamic Programming', 'Breadth-First Search', 'Bitmask', 'C++']