Minimum moves to move a box to their target location

Array Breadth-First Search Heap (Priority Queue) Matrix

49.5% acceptance

Feb 25, 2026

887

A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations. The game is represented by an m x n grid of characters grid where each element is a wall, floor, or box. Your task is to move the box 'B' to the target position 'T' under the following rules: The character 'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell). The character '.' represents the floor which means a free cell to walk. The character '#' represents the wall which means an obstacle (impossible to walk there). There is only one box 'B' and one target cell 'T' in the grid. The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push. The player cannot walk through the box. Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_push_box(grid: Vec<Vec<char>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();

    let mut box_pos = (0, 0);
    let mut player_pos = (0, 0);
    let mut target = (0, 0);

    for i in 0..m {
      for j in 0..n {
        match grid[i][j] {
          'B' => box_pos = (i, j),
          'S' => player_pos = (i, j),
          'T' => target = (i, j),
          _ => {}
        }
      }
    }

    let is_free = |r: i32, c: i32| -> bool {
      r >= 0 && r < m as i32 && c >= 0 && c < n as i32 && grid[r as usize][c as usize] != '#'
    };

    // Check if player can reach (pr, pc) to (tr, tc) without going through box (br, bc)
    let can_reach = |pr: i32, pc: i32, tr: i32, tc: i32, br: i32, bc: i32| -> bool {
      if pr == tr && pc == tc { return true; }
      let mut visited = vec![vec![false; n]; m];
      let mut queue = std::collections::VecDeque::new();
      visited[pr as usize][pc as usize] = true;
      queue.push_back((pr, pc));
      while let Some((r, c)) = queue.pop_front() {
        for (dr, dc) in [(-1i32,0),(1,0),(0,-1i32),(0,1)] {
          let nr = r + dr;
          let nc = c + dc;
          if is_free(nr, nc) && !(nr == br && nc == bc) && !visited[nr as usize][nc as usize] {
            if nr == tr && nc == tc { return true; }
            visited[nr as usize][nc as usize] = true;
            queue.push_back((nr, nc));
          }
        }
      }
      false
    };

    // BFS state: (box_r, box_c, player_r, player_c), count = pushes
    let mut visited = vec![vec![vec![vec![false; n]; m]; n]; m];
    let (br, bc) = box_pos;
    let (pr, pc) = player_pos;
    visited[br][bc][pr][pc] = true;

    let mut queue = std::collections::VecDeque::new();
    queue.push_back((br as i32, bc as i32, pr as i32, pc as i32, 0i32));

    while let Some((br, bc, pr, pc, pushes)) = queue.pop_front() {
      if (br as usize, bc as usize) == target {
        return pushes;
      }

      for (dr, dc) in [(-1i32,0),(1,0),(0,-1i32),(0,1)] {
        let nbr = br + dr;
        let nbc = bc + dc;
        if !is_free(nbr, nbc) { continue; }

        // Player needs to be at br-dr, bc-dc to push in direction dr,dc
        let req_pr = br - dr;
        let req_pc = bc - dc;
        if !is_free(req_pr, req_pc) { continue; }

        if can_reach(pr, pc, req_pr, req_pc, br, bc) {
          let nbr_u = nbr as usize;
          let nbc_u = nbc as usize;
          let br_u = br as usize;
          let bc_u = bc as usize;
          if !visited[nbr_u][nbc_u][br_u][bc_u] {
            visited[nbr_u][nbc_u][br_u][bc_u] = true;
            queue.push_back((nbr, nbc, br, bc, pushes + 1));
          }
        }
      }
    }
    -1
  }
}