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 thegridif 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 thegrid. - 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.lengthn == grid[i].length1 <= m <= 201 <= n <= 20gridcontains only characters'.','#','S','T', or'B'.- There is only one character
'S','B'and'T'in thegrid.
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);
}