Minimum Pushes to Move a Crate to Its Target
A warehouse robot pushes a single crate across a floor grid to a target dock. The robot can walk freely over empty cells but only moves the crate by standing on the opposite side and pushing. Minimize pushes.
Problem
Given a grid with '.' floor, '#' wall, 'S' robot start, 'B' box start, and 'T' target, the robot moves up/down/left/right over floor and can push the box by standing on the cell opposite the push direction (that cell must be floor) so the box advances one cell (its destination must be floor). Return the minimum number of pushes to move the box onto the target, or -1.
Input
A 2D char grid containing exactly one each of 'S', 'B', 'T'.
Output
An integer: minimum pushes, or -1 if unreachable.
Constraints
- 1 <= rows, cols <= 20
- Exactly one 'S', one 'B', one 'T'; the rest are '.' or '#'.
Examples
Example 1
Input
grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#",".","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
Output
3
The robot repositions and pushes the box 3 times to reach T.
Example 2
Input
grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#","#","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
Output
-1
No sequence of pushes brings the box to the target.