BFS+hash map precomputes moves +DP+ mask||319 ms Beats 100.00%
Intuition\n Describe your first thoughts on how to solve this problem. \nTry an optimal solution. From TLE to 917ms(without hash map), finally got 319 ms \n# Ap
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry an optimal solution. From TLE to 917ms(without hash map), finally got 319 ms \n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Construct a hash map `SetP` for `positions` to its corresponding index. To reduce the computational amount for BFS for precompting minimum moves among `positions`.\n2. Define `BFS_minMoves(int idx, vector<vector<int>>& positions)` to compute the distances of `position[idx]` to all positions. The method is standard BFS with the `unordered_map SetP` which just computes enough steps not the whole chess board.\n3. Define `int dfs(bool isBob, int idx, int bMask, vector<vector<int>>& positions)`by using min-max argument which is in fact very similar for solving [Leetcode 1140. Stone Game II](https://leetcode.com/problems/stone-game-ii/solutions/5662804/3d2d-recursive-dp-without-prefix-sum5ms-beats-9400/) \n4. In `maxMoves(int kx, int ky, vector<vector<int>>& positions)`, add starting to positions; then call `build_SetP`(positions)`.\n5. Use a loop to proceed `BFS_minMoves(i, positions)` for i=0,...,|position|-1.\n6. `dfs(0, sz - 1, 1 << (sz - 1),positions)` is the answer.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code||319 ms Beats 100.00%\n```cpp []\nconst int mv[8][2] = {{1, 2},   {2, 1},   {2, -1}, {1, -2},\n                      {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};\nconst int N = 50;\nint D[16][16]; // Store distances between positions (at most 16 positions)\nint sz;\nint dp[2][16][(1 << 16)];\n\nusing int2 = pair<int, int>;\nclass Solution {\npublic:\n    inline bool isInside(int r0, int c0) {\n        return 0 <= r0 && r0 < N && 0 <= c0 && c0 < N;\n    }\n    inline int num(int i, int j){\n        return i*N+j;\n    }\n    unordered_map<int, int> SetP;\n    inline void build_SetP(vector<vector<int>>& positions){\n        int i=0;\n        for(auto& p: positions){\n            SetP[num(p[0], p[1])]=i++;\n        }\n    }\n    // Perform BFS from a single starting position to all other positions\n    void BFS_minMoves(int idx, vector<vector<int>>& positions) {\n        int r0 = positions[idx][0], c0 = positions[idx][1];\n        int dist[N][N]; // Distance from (r0, c0) to all other positions\n        memset(dist, -1, sizeof(dist));\n        queue<int> q;\n        q.push(num(r0, c0));\n        dist[r0][c0] = 0;\n        int cnt=0;\n        while (!q.empty()&& cnt<sz) {\n            int x = q.front(); \n            auto [r, c]=div(x, N);\n            q.pop();\n            int currentD = dist[r][c];\n            if (SetP.count(x)){\n                D[idx][SetP[x]]=currentD;\n                cnt++;\n            }\n            for (int a = 0; a < 8; a++) {\n                int nr = r + mv[a][0], nc = c + mv[a][1];\n                if (isInside(nr, nc) && dist[nr][nc] == -1) {\n                    dist[nr][nc] = currentD + 1;\n                    q.emplace(num(nr, nc));\n                }\n            }\n        }\n    }\n\n    int dfs(bool isBob, int idx, int bMask, vector<vector<int>>& positions) {\n        if (bMask == (1 << sz) - 1)\n            return 0; // All positions visited\n        if (dp[isBob][idx][bMask] != -1)\n            return dp[isBob][idx][bMask];\n\n        int moves = (isBob) ? INT_MAX : 0;\n        for (int i = 0; i < sz; i++) {\n            if (bMask & (1 << i))\n                continue;         // If position i is already visited, skip\n            int dist = D[idx][i]; // Distance between positions idx and i\n            if (isBob)\n                moves =\n                    min(moves, dist + dfs(0, i, bMask | (1 << i),\n                                          positions)); // Bob minimizes moves\n            else\n                moves =\n                    max(moves, dist + dfs(1, i, bMask | (1 << i),\n                                          positions)); // Alice maximizes moves\n        }\n        return dp[isBob][idx][bMask] = moves;\n    }\n\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        positions.push_back({kx, ky}); // add starting to positions\n        sz = positions.size();\n\n        build_SetP(positions);// Build SetPfrom positions\n        // Compute the shortest distances between all pairs of positions\n        for (int i = 0; i < sz; i++)\n            BFS_minMoves(i, positions);\n\n        memset(dp, -1, sizeof(dp)); // Initialize memoization array\n        return dfs(0, sz - 1, 1 << (sz - 1),\n                   positions); // Start DFS from the knight\'s position\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Hash Table', 'Dynamic Programming', 'Breadth-First Search', 'C++']