BFS + Bitmask, ⌛:N^2∗2^N
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n> Note: In this questio
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n> Note: In this question, Memoization approach(Top-down) is more easier to write than Tabulation approach (Bottom-up).\n\n# Complexity\nThe size of chessboard is $$SIZE \\times SIZE$$ and there\'re N pawns.\n- Time complexity: $$O(N^2*2^N + N * SIZE^2)$$\n  * BFS to find the moves b/w each pawn and knight: $$O(N * SIZE^2 + N^2)$$\n  * DP: $$O(N^2*2^N)$$\n  * Total: $$O(N * SIZE^2 + N^2) + O(N^2*2^N) = O(N^2*2^N + N * SIZE^2)$$\n- Space complexity: $$O(N*2^N + SIZE^2)$$\n  * BFS: $$O(N^2 + SIZE^2)$$\n  * DP: $$O(N*2^N)$$\n  * Total: $$O(N^2 + SIZE^2) + O(N*2^N) = O(N*2^N + SIZE^2)$$\n\n# Code\n```cpp []\nstruct Coord {\n    int x, y;\n};\n\nclass Solution {\nprivate:\n    static const int SIZE = 50;\n\npublic:\n    int memo(int** dp, unsigned int bitmask, int pos, int** cost,\n             vector<vector<int>>& positions) {\n        if (dp[bitmask][pos] != 0) {\n            return dp[bitmask][pos];\n        }\n\n        int turn = popcount(bitmask);\n\n        if (turn == positions.size() - 1) { // all pawn has been captured\n            return 0;\n        }\n\n        if (turn % 2 == 1) {\n            dp[bitmask][pos] = INT_MAX;\n        } else {\n            dp[bitmask][pos] = 0;\n        }\n\n        for (int i = 0; i < positions.size() - 1; i++) {\n            if ((bitmask & (1 << i)) == 0) { // unvisited\n                int temp = memo(dp, bitmask | (1 << i), i, cost, positions) +\n                           cost[pos][i];\n\n                if (turn % 2 == 1) {\n                    dp[bitmask][pos] = min(dp[bitmask][pos], temp);\n                } else {\n                    dp[bitmask][pos] = max(dp[bitmask][pos], temp);\n                }\n            }\n        }\n\n        return dp[bitmask][pos];\n    }\n\n    // helper fn for BFS\n    void visit(int x, int y, int moves, int temp[][SIZE], queue<Coord>* q) {\n        if (x < 0 || y < 0 || x >= SIZE || y >= SIZE) {\n            return;\n        }\n\n        if (temp[x][y] == -1) {\n            temp[x][y] = moves;\n            q->push({x, y});\n        }\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        // 16*2500*8 = 3.2e5\n        // dp[bitmask][pos]: (1<<15)*16=5.2e5\n\n        positions.push_back({kx, ky}); // treat original pos as another pawn\n\n        int** cost = new int*[positions.size()];\n        for (int i = 0; i < positions.size(); i++) {\n            cost[i] = new int[positions.size()]();\n        }\n\n        // BFS\n        for (int i = 0; i < positions.size(); i++) {\n            int temp[SIZE][SIZE] = {};\n            fill(&temp[0][0], &temp[0][0] + SIZE * SIZE, -1); // -1: unvisited\n\n            int x_i = positions[i][0];\n            int y_i = positions[i][1];\n\n            queue<Coord> q;\n\n            temp[x_i][y_i] = 0; // visited\n            q.push({x_i, y_i});\n\n            int moves = 1;\n            while (!q.empty()) {\n                for (int _ = q.size(); _ > 0; _--) {\n                    int x = q.front().x;\n                    int y = q.front().y;\n                    q.pop();\n\n                    visit(x + 2, y + 1, moves, temp, &q);\n                    visit(x + 2, y - 1, moves, temp, &q);\n                    visit(x - 2, y + 1, moves, temp, &q);\n                    visit(x - 2, y - 1, moves, temp, &q);\n                    visit(x + 1, y + 2, moves, temp, &q);\n                    visit(x + 1, y - 2, moves, temp, &q);\n                    visit(x - 1, y + 2, moves, temp, &q);\n                    visit(x - 1, y - 2, moves, temp, &q);\n                }\n\n                moves++;\n            }\n\n            for (int j = 0; j < positions.size(); j++) {\n                int x = positions[j][0];\n                int y = positions[j][1];\n\n                cost[i][j] = temp[x][y];\n            }\n        }\n\n        // dp[bitmask][pos], bitmask 00...00 means all uncaptured\n        int** dp = new int*[1 << (positions.size() - 1)];\n        for (int i = 0; i < 1 << (positions.size() - 1); i++) {\n            dp[i] = new int[positions.size()]();\n        }\n\n        return memo(dp, 0, positions.size() - 1, cost, positions);\n    }\n};\n```\n\n---\n# If you have any question or advice, welcome to comment below.
['Array', 'Bit Manipulation', 'Breadth-First Search', 'Bitmask', 'C++']