Practice/Google/Leetcode 1263. Minimum Moves to Move a Box to Their Target Location

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

CodingMust

Problem

You are managing a warehouse robot that needs to push a box to a designated target location on a grid. The grid contains:

• 'S' - the starting position of the robot (player)
• 'B' - the initial position of the box
• 'T' - the target position where the box needs to be pushed
• '.' - empty walkable cells
• '#' - walls that neither the robot nor the box can pass through

The robot can walk freely on empty cells and the target cell. However, the robot cannot walk through the box or walls. To move the box, the robot must be positioned directly adjacent to the box (up, down, left, or right) and push it in a direction away from the robot's position. The box moves one cell in that direction if the destination cell is not a wall.

Your task is to find the minimum number of pushes required to move the box to the target position. Note that the robot can walk any number of steps between pushes, but only the number of pushes counts toward the answer.

Return the minimum number of pushes, or -1 if it's impossible to move the box to the target.

Requirements

1. Calculate the minimum number of box pushes (not player moves) needed to reach the target
2. The player can walk freely on empty cells but cannot pass through walls or the box
3. To push the box, the player must be adjacent to it and push it away from their position
4. The box cannot be pushed through walls
5. Return -1 if the target is unreachable

Constraints

• 1 <= grid.length <= 20
• 1 <= grid[i].length <= 20
• The grid contains exactly one 'S', one 'B', and one 'T'
• The grid is surrounded by walls (all border cells are '#')
• Time complexity should be reasonable for the given grid size
• Space complexity should be O(rows × cols × rows × cols) or better

Examples

Example 1:

Input: grid = [ ["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".",".","B","."], ["#",".","#","#","S","#"], ["#","#","#","#","#","#"] ] Output: 3 Explanation: The player walks to position the box, then pushes it left 3 times to reach the target at (1, 1).

Example 2:

Input: grid = [ ["#","#","#","#","#"], ["#","S","B","T","#"], ["#","#","#","#","#"] ] Output: -1 Explanation: The box is trapped between the player and walls. It's impossible to get behind the box to push it toward the target.

Example 3:

Input: grid = [ ["#","#","#","#"], ["#","S","T","#"], ["#","#","#","#"] ] Output: 0 Explanation: The box is already at the target position, requiring 0 pushes.