My Solution
\n/**\n * Time Complexity: O(n_positions * n_positions * (2 ^ n_positions))\n * Space Complexity: O(n_positions * (2 ^ n_positions))\n * where `n_positions` is 
```\n/**\n * Time Complexity: O(n_positions * n_positions * (2 ^ n_positions))\n * Space Complexity: O(n_positions * (2 ^ n_positions))\n * where `n_positions` is the length of the vector `positions`\n */\nclass Solution {\n private:\n  static constexpr int invalid_index = -1;\n  static constexpr int n = 50;\n  \n public:\n  int maxMoves(const int kx, const int ky, const vector<vector<int>> &positions) {\n    const int n_positions = static_cast<int>(positions.size());\n    vector<vector<int>> position_indices(n, vector<int>(n, invalid_index));\n    for (int i = 0; i < n_positions; ++i) {\n      position_indices[positions[i].front()][positions[i].back()] = i;\n    }\n    \n    int distance_from_knight_to_pawn[n_positions];\n    memset(distance_from_knight_to_pawn, -1, sizeof(distance_from_knight_to_pawn));\n    bfs(kx, ky, position_indices, n_positions, distance_from_knight_to_pawn);\n    int distance_between_pawns[n_positions][n_positions];\n    memset(distance_between_pawns, -1, sizeof(distance_between_pawns));\n    for (int start = 0; start < n_positions; ++start) {\n      bfs(positions[start].front(), positions[start].back(), position_indices, n_positions, distance_between_pawns[start]);\n    }\n\n    const int layouts = 1 << n_positions;\n    const int all_non_killed_layout = layouts - 1;\n    int dp[layouts][n_positions];\n    memset(dp, 0, sizeof(dp));\n    for (int non_killed_layout = 1; non_killed_layout < layouts - 1; ++non_killed_layout) {\n      const int killed_layout = all_non_killed_layout ^ non_killed_layout;\n      const int killed_number = get_bit_ones(killed_layout);\n      const bool is_alice_turn = (killed_number & 0b1) == 0b0;\n      for (int killed = 0; killed < n_positions; ++killed) {\n        if (((killed_layout >> killed) & 0b1) == 0b0) {\n          continue;\n        }\n        \n        dp[non_killed_layout][killed] = is_alice_turn ? 0 : numeric_limits<int>::max();\n        for (int non_killed = 0; non_killed < n_positions; ++non_killed) {\n          if (((non_killed_layout >> non_killed) & 0b1) == 0b0) {\n            continue;\n          }\n          \n          /**\n           * the knight moves from the `killed`\'th pawn to the `non_killed`\'th pawn\n           * to kill the `non_killed` pawn\n           */\n          if (is_alice_turn) {\n            // it\'s alice\'s turn\n            dp[non_killed_layout][killed] = max(\n              dp[non_killed_layout][killed],\n              dp[non_killed_layout ^ (1 << non_killed)][non_killed] + distance_between_pawns[killed][non_killed]\n            );\n          } else {\n            // it\'s bob\'s turn\n            dp[non_killed_layout][killed] = min(\n              dp[non_killed_layout][killed],\n              dp[non_killed_layout ^ (1 << non_killed)][non_killed] + distance_between_pawns[killed][non_killed]\n            );\n          }\n        }\n      }\n    }\n\n    int ret = 0;\n    for (int pawn = 0; pawn < n_positions; ++pawn) {\n      /**\n       * the knight moves from its initial position (kx, ky) to the `pawn`\'th pawn to kill it\n       */\n      ret = max(ret, dp[all_non_killed_layout ^ (1 << pawn)][pawn] + distance_from_knight_to_pawn[pawn]);\n    }\n    return ret;\n  }\n  \n private:\n  void bfs(const int start_x,\n           const int start_y,\n           const vector<vector<int>> &position_indices,\n           const int n_positions,\n           int *distances) {\n    constexpr int directions[] = {2, 1, -2, 1, 2, -1, -2, -1, 2};\n    constexpr int n_directions = 8;\n    using q_node_t = array<int, 2>;   // {x, y}\n    bool visited[n][n]{};\n    queue<q_node_t> q({q_node_t{start_x, start_y}});\n    visited[start_x][start_y] = true;\n    for (int reached = 0, distance = 0; !q.empty() && reached < n_positions; ++distance) {\n      for (size_t i = q.size(); i > 0; --i) {\n        const auto [x, y] = q.front();\n        if (position_indices[x][y] != invalid_index) {\n          distances[position_indices[x][y]] = distance;\n          if (++reached == n_positions) {\n            break;\n          }\n        }\n        q.pop();\n        for (int d = 0; d < n_directions; ++d) {\n          const int nx = x + directions[d];\n          const int ny = y + directions[d + 1];\n          if (nx > -1 && nx < n && ny > -1 && ny < n && !visited[nx][ny]) {\n            q.emplace(q_node_t{nx, ny});\n            visited[nx][ny] = true;\n          }\n        }\n      }\n    }\n  }\n  \n  int get_bit_ones(const int num) {\n    int ret = 0;\n    for (int number = num; number > 0; number &= number - 1) {\n      ++ret;\n    }\n    return ret;\n  }\n};\n```
[]