Beats 100% in TC ✔️ || Simple Clean Approach || BitMask DP || BFS || Pre Computation
You can Upvote If you\'ve liked it\n# Beats 100% in TC\n\n\n# C++ Best Code : \n\n// 4 D array for distance from (x, y) to some (p, q)\nint dist[50][50][50][50]
**You can Upvote If you\'ve liked it**\n# Beats 100% in TC\n![image](https://assets.leetcode.com/users/images/961e5585-c2d5-4234-8fbc-21472100a613_1725822899.6437142.png)\n\n# C++ Best Code : \n```\n// 4 D array for distance from (x, y) to some (p, q)\nint dist[50][50][50][50];\n// 8 Possible Direction for Knight to move\nint dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}; \nint dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};\n\n// Simple BFS\nvoid BFS(int stx, int sty) {\n    // add the current pos to queue\n    queue<pair<pair<int, int>, int>> q;\n    q.push({{stx, sty}, 0});\n    dist[stx][sty][stx][sty] = 0;\n\n    while(!q.empty()) {\n        // Standard BFS Case\n        int x = q.front().first.first;\n        int y = q.front().first.second;\n        int d = q.front().second;\n        q.pop();\n\n        for(int i = 0; i < 8; i++) {\n            int nyx = x + dx[i];\n            int nyy = y + dy[i];\n            // Make sure the condition...if dist already calculated or not\n            if(nyx >= 0 and nyy >= 0 and nyx < 50 and nyy < 50 and dist[stx][sty][nyx][nyy] == -1) {\n                dist[stx][sty][nyx][nyy] = d + 1;\n                q.push({{nyx, nyy}, d + 1});\n            }\n        }\n    }\n}\n\nvoid preCompute() {\n    static bool done = false;\n    if(done)\n        return;\n    memset(dist, -1, sizeof(dist));\n    // Check for all the positions and pass to the BFS func\n    for(int i = 0; i < 50; i++) {\n        for(int j = 0; j < 50; j++) {\n            // Check if it is already calculated\n            if(dist[i][j][i][j] == -1) {\n                BFS(i, j);\n            }\n        }\n    }\n    done = true;\n}\n\nclass Solution {\npublic:\n    vector<vector<vector<int>>> dp;\n    \n    int helper_function(int curr, int mask, int turn, vector<vector<int>>& positions) {\n        int n = positions.size();\n        // Here we are checking if all the positions are covered or not\n        if(mask == (1 << n) - 1)\n            return 0;\n        // Check if this state is already being calculated or not\n        if(dp[curr][mask][turn] != -1)\n            return dp[curr][mask][turn];\n        \n        // this is the current coordinate\n        int x = positions[curr][0];\n        int y = positions[curr][1];\n        int ans;\n        \n        // Alice turn\n        if(!turn) {\n            // Alice wants to maximize the answer\n            ans = INT_MIN;\n            for(int i = 0; i < n; i++) {\n                // Check if this pawn is taken or not\n                // if the bit is set then taken and move to the next pawn\n                if(mask & (1 << i))\n                    continue;\n                // Current pawn position\n                int pawnX = positions[i][0];\n                int pawnY = positions[i][1];\n                // pawn distance from the knight position\n                int d = dist[x][y][pawnX][pawnY];\n                \n                // mark it right and check for the next position\n                ans = max(ans, d + helper_function(i, mask | (1 << i), !turn, positions));\n            }\n        }\n        // Bob turn\n        else {\n            // Bob wants to minimize the answer\n            ans = INT_MAX;\n            for(int i = 0; i < n; i++) {\n                // Check if this pawn is taken or not\n                // if the bit is set then taken and move to the next pawn\n                if(mask & (1 << i))\n                    continue;\n                // Current pawn position\n                int pawnX = positions[i][0];\n                int pawnY = positions[i][1];\n                // pawn distance from the knight position\n                int d = dist[x][y][pawnX][pawnY];\n                \n                // mark it right and check for the next position\n                ans = min(ans, d + helper_function(i, mask | (1 << i), !turn, positions));\n            }\n        }\n        \n        return dp[curr][mask][turn] = ans;\n    }\n    \n    // This is just a checker function for dist vector\n    void checker() {\n        for(int i = 0; i < 50; i++) {\n            for(int j = 0; j < 50; j++) {\n                for(int p = 0; p < 50; p++) {\n                    for(int q = 0; q < 50; q++) {\n                        cout << dist[i][j][p][q] << " ";\n                    }\n                }\n                cout << endl;\n            }\n        }\n    }\n    \n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        positions.push_back({kx, ky});\n        // This is the precompute function which only runs for once ,\n        // We\'ve already initialize the static variable \n        preCompute();\n        // checker();\n        int n = positions.size();\n        // Define the 3D DP state for pos, masking, and for two players\n        dp.resize(n, vector<vector<int>>(1 << n, vector<int>(2,-1)));\n        \n        // Pass to the helper function\n        return helper_function(n-1, (1<<(n-1)), 0, positions);\n    }\n};\n```\n\n*TLE Has made it really easy*\n\n
['Dynamic Programming', 'Breadth-First Search', 'Graph', 'Memoization', 'C']