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`.

1263. Minimum Moves to Move a Box to Their Target Location
``````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);
}
``````