BFS to precalculate no of moves, DFS with memoization
\n# Intuition\n1. Calculate all the possible N ^ M distances using BFS for pawns, every distance to go from pawn i to pawn j using the knight.\n2. The start pos
\n# Intuition\n1. Calculate all the possible N ^ M distances using BFS for pawns, every distance to go from pawn i to pawn j using the knight.\n2. The start position could be considered pawn.\n3. Use DFS to calculate all the possible moves for each player , represented by turn. from lastPos to the i next position, i is a pawn position not taken.\n4. Use memoization to store the calculated values.\nBitmask is used to calculate which are the positions(for pawns) already taken.\n \nUsually the bitmask technique is used to form groups.\n> E.g. if we have positions woth 3 elements (indexes 0, 1, 2),the groups which can be formed are the following:\n{} -> 000 (bit mask for none)\n{0} -> 001\n{1} -> 010 (2 ^ 1) is set to 1\n{2} -> 100 (2^2 is set to 1)\n{0,1} -> 011(2^0 and 2^1 are set t0 1)\n{0,2} -> 101(2^0 and 2^2 are set to 1)\n{1,2} -> 110(2^1 and 2^2 are set to 1)\n{0,1,2}->111 (2^2, 2^1, 2^0 all are set to 1)\n\nLesson learned is always efficient to use fixed array values than vector<vector<int>> in case of the dp[][]. I also got TLE because I used unordered_map<int, int> instead of d[50][50]. The unordered_map<int, int> was used with normalizing positions as i * 100 + j. TLE submission using unordered_map can be found [here.](https://leetcode.com/problems/maximum-number-of-moves-to-kill-all-pawns/submissions/1403909326/) \n\n\n\uD83D\uDCAA\uD83D\uDE80Keep leetcoding! Keep improving!\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<vector<int>>knight = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};\n    int dp[17][32769] = {}, dist[17][17] = {};\n    vector<vector<int>> ps;\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        positions.push_back({kx, ky});\n        int n = positions.size();\n        ps = positions;\n       \n        for (int i = 0; i < n; i++) {\n           bfs(i);\n        }\n      \n        return dfs(n - 1, 0, 0, n);\n    }\n\n    int dfs(int lastPos, int turn, int mask, int n) {\n        if ((turn + 1) >= n) {\n            return 0;\n        }\n        if (dp[lastPos][mask] != 0)\n            return dp[lastPos][mask];\n        bool isAlice = turn % 2 == 0;\n        int turnRes = isAlice ? 0 : INT_MAX;   \n        for (int i = 0; i < n - 1; i++) {\n            if (((1 << i) & mask) == 0) { //check position i is unused if 2^i & mask == 0\n                int res = dist[lastPos][i] + dfs(i, turn + 1, mask | (1 << i), n);\n                turnRes = isAlice ? max(res, turnRes) : min(res, turnRes);\n            }\n        }\n        dp[lastPos][mask] = turnRes;\n        return dp[lastPos][mask];\n    }\n    void bfs(int startPos) {\n        int n = ps.size(), sx = ps[startPos][0], sy = ps[startPos][1];\n        int d[50][50] = {}; //distance for each position\n        queue<pair<int,int>>q; \n        q.push({sx, sy});\n        d[sx][sy] = 0;\n        while(!q.empty()) {\n            auto f = q.front();\n            q.pop();\n            for (int i = 0; i < 8; i++) {\n                int ii = f.first + knight[i][0];\n                int jj = f.second + knight[i][1];\n                if (ii >= 0 && ii < 50 && jj >= 0 && jj < 50)\n                    if (d[ii][jj] == 0 && !(ii == sx && jj == sy)) {\n                        d[ii][jj] = d[f.first] [f.second] + 1;\n                        q.push({ii, jj});\n                    }\n            }\n        }\n        \n        for (int i = 0; i < n; i++) {\n            dist[startPos][i] = d[ps[i][0]][ps[i][1]];\n        }\n    }\n};\n```
['Bit Manipulation', 'Breadth-First Search', 'Bitmask', 'C++']