Maximum number of moves to kill all pawns

Array Math Bit Manipulation Breadth-First Search Game Theory Bitmask

33.7% acceptance

Feb 25, 2026

144

There is a 50 x 50 chessboard with one knight and some pawns on it. You are given two integers kx and ky where (kx, ky) denotes the position of the knight, and a 2D array positions where positions[i] = [xi, yi] denotes the position of the pawns. Alice and Bob play a turn-based game, where Alice goes first. The player selects a pawn that still exists and captures it with the knight in fewest possible moves. Alice maximizes, Bob minimizes the total moves. Return the maximum total number of moves Alice can achieve.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_moves(kx: i32, ky: i32, positions: Vec<Vec<i32>>) -> i32 {
    let n = positions.len();
    // BFS to compute min knight moves between any two positions (including start)
    // Positions indexed: 0..n = pawns, n = knight start
    let mut all_pos: Vec<(i32, i32)> = positions.iter().map(|p| (p[0], p[1])).collect();
    all_pos.push((kx, ky));
    let m = all_pos.len(); // n+1
    
    // dist[i][j] = BFS knight moves from all_pos[i] to all_pos[j]
    let bfs = |sr: i32, sc: i32| -> Vec<Vec<i32>> {
      let mut dist = vec![vec![-1i32; 50]; 50];
      let mut q = std::collections::VecDeque::new();
      dist[sr as usize][sc as usize] = 0;
      q.push_back((sr, sc));
      let moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)];
      while let Some((r, c)) = q.pop_front() {
        for (dr, dc) in moves {
          let nr = r + dr; let nc = c + dc;
          if nr >= 0 && nr < 50 && nc >= 0 && nc < 50 && dist[nr as usize][nc as usize] == -1 {
            dist[nr as usize][nc as usize] = dist[r as usize][c as usize] + 1;
            q.push_back((nr, nc));
          }
        }
      }
      dist
    };
    
    // dist_matrix[i][j] = knight moves to go from position i to capture pawn j
    let mut dm = vec![vec![0i32; n]; m];
    for i in 0..m {
      let (r, c) = all_pos[i];
      let bd = bfs(r, c);
      for j in 0..n {
        let (rj, cj) = all_pos[j];
        dm[i][j] = bd[rj as usize][cj as usize];
      }
    }
    
    // dp[mask][last] = optimal total moves when `mask` pawns have been captured
    // and knight is currently at position `last` (index into all_pos, n = start)
    // Alice picks first, last, ...(even turns = 0-indexed), Bob picks odd turns
    // Alice maximizes, Bob minimizes
    // Number of turns = popcount(mask)
    let full = (1usize << n) - 1;
    let mut dp = vec![vec![0i32; n + 1]; 1 << n];
    
    // Fill from full mask down to 0 (decreasing order so dp[new_mask] is computed first)
    for mask in (0..=(full as usize)).rev() {
      let turn = mask.count_ones() as usize; // whose turn it is (0=Alice, 1=Bob)
      let alice = turn % 2 == 0;
      for last in 0..=n {
        if mask == full { continue; }
        // last is current knight pos (n = initial)
        let mut best = if alice { i32::MIN } else { i32::MAX };
        for j in 0..n {
          if mask & (1 << j) == 0 {
            // capture pawn j
            let cost = dm[last][j];
            let new_mask = mask | (1 << j);
            let val = cost + dp[new_mask][j];
            if alice {
              if val > best { best = val; }
            } else {
              if val < best { best = val; }
            }
          }
        }
        if best != i32::MIN && best != i32::MAX {
          dp[mask][last] = best;
        }
      }
    }
    
    dp[0][n]
  }
}