Skip to content

3283. Maximum Number of Moves to Kill All Pawns 👍

  • Time: $O(n \cdot 50^2 + n^2 \cdot 2^n)$
  • Space: $O(n^2 + n \cdot 2^n) = O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
 public:
  int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
    const int n = positions.size();
    positions.push_back({kx, ky});
    unordered_map<int, int> hashedPositionToIndex;
    // dist[i][j] := the minimum distance from positions[i] to positions[j]
    vector<vector<int>> dist(n + 1, vector<int>(n + 1));

    for (int i = 0; i < positions.size(); ++i) {
      const int x = positions[i][0];
      const int y = positions[i][1];
      hashedPositionToIndex[hash(x, y)] = i;
    }

    for (int sourceIndex = 0; sourceIndex < n + 1; ++sourceIndex)
      bfs(positions, sourceIndex, hashedPositionToIndex, dist);

    const int maxMask = 1 << (n + 1);
    // dp[i][mask][turn] := the maximum (Alice) or the minimum (Bob) cost to
    // kill all pawns, where i is the current pawn, mask is the set of pawns
    // that have been killed, and turn is the current player's turn (0 for Alice
    // and 1 for Bob)
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(1 << (n + 1), vector<int>(2)));

    for (int i = 0; i < n + 1; ++i)
      for (int mask = 0; mask < maxMask - 1; ++mask)
        dp[i][mask] = {-kMax, kMax};

    for (int mask = maxMask - 2; mask >= 0; --mask)
      for (int i = 0; i < n + 1; ++i)
        for (int turn = 0; turn < 2; ++turn)
          for (int j = 0; j < n; ++j) {
            if (mask >> j & 1)
              continue;
            const int moves = dist[i][j] + dp[j][mask | 1 << j][1 - turn];
            dp[i][mask][turn] = turn == 0 ? max(dp[i][mask][turn], moves)
                                          : min(dp[i][mask][turn], moves);
          }

    // Returns the maximum cost to kill all pawns, i.e., the original positions
    // array without the knight (kx, ky).
    return dp[n][1 << n][0];
  }

 private:
  static constexpr int kSize = 50;
  static constexpr int kMax = 1'000'000;
  static constexpr int kDirs[8][2] = {{1, 2},   {2, 1},   {2, -1}, {1, -2},
                                      {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

  int hash(int x, int y) {
    return x * kSize + y;
  }

  // Computes the distance between positions[sourceIndex] and other positions.
  void bfs(const vector<vector<int>>& positions, int sourceIndex,
           const unordered_map<int, int>& hashedPositionToIndex,
           vector<vector<int>>& dist) {
    const int sx = positions[sourceIndex][0];
    const int sy = positions[sourceIndex][1];
    queue<pair<int, int>> q{{{sx, sy}}};
    vector<vector<bool>> seen(kSize, vector<bool>(kSize));
    seen[sx][sy] = true;
    int seenPositions = 0;

    for (int step = 0; !q.empty() && seenPositions < positions.size(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        if (const auto it = hashedPositionToIndex.find(hash(i, j));
            it != end(hashedPositionToIndex)) {
          dist[sourceIndex][it->second] = step;
          ++seenPositions;
        }
        for (const auto& [dx, dy] : kDirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x >= kSize || y < 0 || y >= kSize)
            continue;
          if (seen[x][y])
            continue;
          q.emplace(x, y);
          seen[x][y] = true;
        }
      }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
  public int maxMoves(int kx, int ky, int[][] positions) {
    final int n = positions.length;
    List<int[]> positionsList = new ArrayList<>(List.of(positions));
    positionsList.add(new int[] {kx, ky});
    Map<Integer, Integer> hashedPositionToIndex = new HashMap<>();
    // dist[i][j] := the minimum distance from positions[i] to positions[j]
    int[][] dist = new int[n + 1][n + 1];

    for (int i = 0; i < positionsList.size(); ++i) {
      final int x = positionsList.get(i)[0];
      final int y = positionsList.get(i)[1];
      hashedPositionToIndex.put(hash(x, y), i);
    }

    for (int sourceIndex = 0; sourceIndex < n + 1; ++sourceIndex)
      bfs(positionsList, sourceIndex, hashedPositionToIndex, dist);

    int MAX_MASK = 1 << (n + 1);
    // dp[i][mask][turn] := the maximum (Alice) or the minimum (Bob) cost to
    // kill all pawns, where i is the current pawn, mask is the set of pawns
    // that have been killed, and turn is the current player's turn (0 for Alice
    // and 1 for Bob)
    int[][][] dp = new int[n + 1][1 << (n + 1)][2];

    for (int i = 0; i < n + 1; ++i)
      for (int mask = 0; mask < MAX_MASK - 1; ++mask)
        dp[i][mask] = new int[] {-MAX, MAX};

    for (int mask = MAX_MASK - 2; mask >= 0; --mask)
      for (int i = 0; i < n + 1; ++i)
        for (int turn = 0; turn < 2; ++turn)
          for (int j = 0; j < n; ++j) {
            if ((mask >> j & 1) == 1)
              continue;
            final int moves = dist[i][j] + dp[j][mask | 1 << j][1 - turn];
            dp[i][mask][turn] = turn == 0 ? Math.max(dp[i][mask][turn], moves) //
                                          : Math.min(dp[i][mask][turn], moves);
          }

    // Returns the maximum cost to kill all pawns, i.e., the original positions
    // array without the knight (kx, ky).
    return dp[n][1 << n][0];
  }

  private static final int SIZE = 50;
  private static final int MAX = 1_000_000;
  private static final int[][] DIRS = {{1, 2},   {2, 1},   {2, -1}, {1, -2},
                                       {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

  private int hash(int x, int y) {
    return x * SIZE + y;
  }

  // Computes the distance between positions[sourceIndex] and other positions.
  private void bfs(List<int[]> positions, int sourceIndex,
                   Map<Integer, Integer> hashedPositionToIndex, int[][] dist) {
    final int sx = positions.get(sourceIndex)[0];
    final int sy = positions.get(sourceIndex)[1];
    Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(sx, sy)));
    boolean[][] seen = new boolean[SIZE][SIZE];
    seen[sx][sy] = true;
    int seenPositions = 0;

    for (int step = 0; !q.isEmpty() && seenPositions < positions.size(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().getKey();
        final int j = q.poll().getValue();
        final int hashedPosition = hash(i, j);
        if (hashedPositionToIndex.containsKey(hashedPosition)) {
          dist[sourceIndex][hashedPositionToIndex.get(hashedPosition)] = step;
          ++seenPositions;
        }
        for (int[] dir : DIRS) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x >= SIZE || y < 0 || y >= SIZE)
            continue;
          if (seen[x][y])
            continue;
          q.offer(new Pair<>(x, y));
          seen[x][y] = true;
        }
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution:
  def __init__(self):
    self.SIZE = 50
    self.MAX = 1_000_000
    self.DIRS = ((1, 2), (2, 1), (2, -1), (1, -2),
                 (-1, -2), (-2, -1), (-2, 1), (-1, 2))

  def maxMoves(self, kx: int, ky: int, positions: list[list[int]]) -> int:
    n = len(positions)
    positions.append([kx, ky])
    hashedPositionToIndex = {}
    # dist[i][j] := the minimum distance from positions[i] to positions[j]
    dist = [[0] * (n + 1) for _ in range(n + 1)]

    for i, (x, y) in enumerate(positions):
      hashedPositionToIndex[self._hash(x, y)] = i

    for sourceIndex in range(n + 1):
      self._bfs(positions, sourceIndex, hashedPositionToIndex, dist)

    MAX_MASK = 1 << (n + 1)
    # dp[i][mask][turn] := the maximum (Alice) or the minimum (Bob) cost to
    # kill all pawns, where i is the current pawn, mask is the set of pawns
    # that have been killed, and turn is the current player's turn (0 for Alice
    # and 1 for Bob)
    dp = [[[0, 0]
          for _ in range(1 << (n + 1))]
          for _ in range(n + 1)]

    for i in range(n + 1):
      for mask in range(MAX_MASK - 1):
        dp[i][mask] = [-self.MAX, self.MAX]

    for mask in range(MAX_MASK - 2, -1, -1):
      for i in range(n + 1):
        for turn in range(2):
          for j in range(n):
            if mask >> j & 1:
              continue
            moves = dist[i][j] + dp[j][mask | 1 << j][1 - turn]
            dp[i][mask][turn] = (max(dp[i][mask][turn], moves) if turn == 0 else
                                 min(dp[i][mask][turn], moves))

    # Returns the maximum cost to kill all pawns, i.e., the original positions
    # array without the knight (kx, ky).
    return dp[n][1 << n][0]

  def _hash(self, x: int, y: int) -> int:
    return x * self.SIZE + y

  def _bfs(
      self,
      positions: list[list[int]],
      sourceIndex: int,
      hashedPositionToIndex: dict[int, int],
      dist: list[list[int]]
  ) -> None:
    """
    Computes the distance between positions[sourceIndex] and other positions.
    """
    sx, sy = positions[sourceIndex]
    q = collections.deque([(sx, sy)])
    seen = {(sx, sy)}
    seenPositions = 0

    step = 0
    while q and seenPositions < len(positions):
      for _ in range(len(q)):
        i, j = q.popleft()
        hashedPosition = self._hash(i, j)
        if hashedPosition in hashedPositionToIndex:
          dist[sourceIndex][hashedPositionToIndex[hashedPosition]] = step
          seenPositions += 1
        for dx, dy in self.DIRS:
          x = i + dx
          y = j + dy
          if x < 0 or x >= self.SIZE or y < 0 or y >= self.SIZE:
            continue
          if (x, y) in seen:
            continue
          q.append((x, y))
          seen.add((x, y))
      step += 1