1263. Minimum Moves to Move a Box to Their Target Location

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 a grid of size m x n, where each element is a wall, floor, or a box.

Your task is move the box 'B' to the target position 'T' under the following rules:

  • Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
  • Floor is represented by character '.' that means free cell to walk.
  • Wall is represented by character '#' that means 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.

 

Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 20
  • 1 <= n <= 20
  • grid contains only characters '.', '#''S' , 'T', or 'B'.
  • There is only one character 'S', 'B' and 'T' in the grid.

Rust Solution

struct Solution;

use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashSet;

type State = (i32, i32, i32, i32);

impl Solution {
    fn min_push_box(grid: Vec<Vec<char>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut floors: HashSet<(i32, i32)> = HashSet::new();
        let mut state = (0, 0, 0, 0);
        let mut t = (0, 0);
        for i in 0..n {
            for j in 0..m {
                match grid[i][j] {
                    'S' => {
                        state.0 = i as i32;
                        state.1 = j as i32;
                        floors.insert((state.0, state.1));
                    }
                    'B' => {
                        state.2 = i as i32;
                        state.3 = j as i32;
                        floors.insert((state.2, state.3));
                    }
                    'T' => {
                        t = (i as i32, j as i32);
                        floors.insert(t);
                    }
                    '.' => {
                        floors.insert((i as i32, j as i32));
                    }
                    _ => {}
                }
            }
        }
        let mut queue: BinaryHeap<(Reverse<i32>, State)> = BinaryHeap::new();
        queue.push((Reverse(0), state));
        let mut visited: HashSet<State> = HashSet::new();
        visited.insert(state);
        let dirs = vec![(1, 0), (0, 1), (-1, 0), (0, -1)];
        while let Some((Reverse(step), state)) = queue.pop() {
            if (state.2, state.3) == t {
                return step;
            }
            for (di, dj) in &dirs {
                let pi = state.0 + di;
                let pj = state.1 + dj;
                let bi = state.2;
                let bj = state.3;
                if (state.2, state.3) == (pi, pj) {
                    let next_state = (pi, pj, bi + di, bj + dj);
                    if floors.contains(&(bi, bj)) && visited.insert(next_state) {
                        queue.push((Reverse(step + 1), next_state));
                    }
                } else {
                    let next_state = (pi, pj, bi, bj);
                    if floors.contains(&(pi, pj)) && visited.insert(next_state) {
                        queue.push((Reverse(step), next_state));
                    }
                }
            }
        }
        -1
    }
}

#[test]
fn test() {
    let grid = vec_vec_char![
        ['#', '#', '#', '#', '#', '#'],
        ['#', 'T', '#', '#', '#', '#'],
        ['#', '.', '.', 'B', '.', '#'],
        ['#', '.', '#', '#', '.', '#'],
        ['#', '.', '.', '.', 'S', '#'],
        ['#', '#', '#', '#', '#', '#']
    ];
    let res = 3;
    assert_eq!(Solution::min_push_box(grid), res);
    let grid = vec_vec_char![
        ['#', '#', '#', '#', '#', '#'],
        ['#', 'T', '#', '#', '#', '#'],
        ['#', '.', '.', 'B', '.', '#'],
        ['#', '#', '#', '#', '.', '#'],
        ['#', '.', '.', '.', 'S', '#'],
        ['#', '#', '#', '#', '#', '#']
    ];
    let res = -1;
    assert_eq!(Solution::min_push_box(grid), res);
    let grid = vec_vec_char![
        ['#', '#', '#', '#', '#', '#'],
        ['#', 'T', '.', '.', '#', '#'],
        ['#', '.', '#', 'B', '.', '#'],
        ['#', '.', '.', '.', '.', '#'],
        ['#', '.', '.', '.', 'S', '#'],
        ['#', '#', '#', '#', '#', '#']
    ];
    let res = 5;
    assert_eq!(Solution::min_push_box(grid), res);
    let grid = vec_vec_char![
        ['#', '#', '#', '#', '#', '#', '#'],
        ['#', 'S', '#', '.', 'B', 'T', '#'],
        ['#', '#', '#', '#', '#', '#', '#']
    ];
    let res = -1;
    assert_eq!(Solution::min_push_box(grid), res);
    let grid = vec_vec_char![
        ['.', '.', '#', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '#', '.', '#', 'B', '#', '.', '#', '.', '.'],
        ['.', '#', '.', '.', '.', '.', '.', '.', 'T', '.'],
        ['#', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '.', '.', '.', '#'],
        ['.', '.', '.', '.', '.', '.', '.', '.', '#', '.'],
        ['.', '.', '.', '#', '.', '.', '#', '#', '.', '.'],
        ['.', '.', '.', '.', '#', '.', '.', '#', '.', '.'],
        ['.', '#', '.', 'S', '.', '.', '.', '.', '.', '.'],
        ['#', '.', '.', '#', '.', '.', '.', '.', '.', '#']
    ];
    let res = 5;
    assert_eq!(Solution::min_push_box(grid), res);
}

Having problems with this solution? Click here to submit an issue on github.