Minimum moves to spread stones over grid

Array Dynamic Programming Backtracking Bit Manipulation Matrix Bitmask

45.4% acceptance

Feb 25, 2026

553

You are given a 0-indexed 2D integer matrix grid of size 3 * 3, representing the number of stones in each cell. The grid contains exactly 9 stones, and there can be multiple stones in a single cell. In one move, you can move a single stone from its current cell to any other cell if the two cells share a side. Return the minimum number of moves required to place one stone in each cell.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_moves(grid: Vec<Vec<i32>>) -> i32 {
    let mut excess: Vec<(i32, i32, i32)> = vec![]; // (row, col, extra)
    let mut deficit: Vec<(i32, i32)> = vec![];
    for i in 0..3 { for j in 0..3 {
      if grid[i][j] > 1 { excess.push((i as i32, j as i32, grid[i][j] - 1)); }
      else if grid[i][j] == 0 { deficit.push((i as i32, j as i32)); }
    }}
    // Try all permutations matching excess stone sources to deficit cells
    let _def_n = deficit.len();
    let mut ans = i32::MAX;
    fn _permute(
      perm: &mut Vec<usize>, used: &mut Vec<bool>,
      excess: &[(i32, i32, i32)], deficit: &[(i32, i32)],
      def_n: usize, ans: &mut i32
    ) {
      if perm.len() == def_n {
        let mut cost = 0i32;
        let mut idx = 0;
        for &ei in perm.iter() {
          let (er, ec, _) = excess[ei];
          let (dr, dc) = deficit[idx];
          cost += (er - dr).abs() + (ec - dc).abs();
          idx += 1;
        }
        *ans = (*ans).min(cost);
        return;
      }
      for i in 0..excess.len() {
        if !used[i] {
          let avail = excess[i].2 as usize;
          let perm_count = perm.iter().filter(|&&x| x == i).count();
          if perm_count < avail {
            used[i] = perm_count + 1 >= avail;
            perm.push(i);
            _permute(perm, used, excess, deficit, def_n, ans);
            perm.pop();
            used[i] = false;
          }
        }
      }
    }

    // Simpler approach: min-cost matching via brute force permutations
    // Since max 9 deficit cells and small grid, use BFS min-cost
    let mut exs: Vec<(i32, i32)> = vec![];
    for (r, c, ex) in &excess { for _ in 0..*ex { exs.push((*r, *c)); } }
    // Generate all permutations of exs for matching to deficit
    fn perm_cost(perm: &[usize], exs: &[(i32,i32)], deficit: &[(i32,i32)]) -> i32 {
      perm.iter().zip(deficit.iter()).map(|(&ei, &(dr, dc))| {
        let (er, ec) = exs[ei];
        (er - dr).abs() + (ec - dc).abs()
      }).sum()
    }
    fn gen_perms(mut cur: Vec<usize>, used: &mut Vec<bool>, n: usize, results: &mut Vec<Vec<usize>>) {
      if cur.len() == n { results.push(cur); return; }
      for i in 0..used.len() {
        if !used[i] { used[i] = true; cur.push(i); gen_perms(cur.clone(), used, n, results); cur.pop(); used[i] = false; }
      }
    }
    let m = deficit.len();
    let mut used = vec![false; exs.len()];
    let mut results = vec![];
    gen_perms(vec![], &mut used, m, &mut results);
    for p in &results { ans = ans.min(perm_cost(p, &exs, &deficit)); }
    if ans == i32::MAX { ans = 0; }
    ans
  }
}