Watch 8 video solutions for Minimum Moves to Move a Box to Their Target Location, a hard level problem involving Array, Breadth-First Search, Heap (Priority Queue). This walkthrough by Hua Hua has 3,698 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A 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 an m x n grid of characters grid where each element is a wall, floor, or box.
Your task is to move the box 'B' to the target position 'T' under the following rules:
'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell).'.' represents the floor which means a free cell to walk.'#' represents the wall which means an obstacle (impossible to walk there).'B' and one target cell 'T' in the grid.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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid contains only characters '.', '#', 'S', 'T', or 'B'.'S', 'B', and 'T' in the grid.Problem Overview: You are given a grid with walls, a player, a box, and a target. The player can move freely but can only push (not pull) the box. The task is to compute the minimum number of pushes required to move the box to the target cell.
Approach 1: Breadth-First Search with State Tracking (O((mn)^2) time, O((mn)^2) space)
Model the puzzle as a state search where each state contains both the box position and the player position. The BFS queue prioritizes states by the number of pushes, not simple movements. When the player moves behind the box and pushes it, a new state is created with the updated box location. Before each push, run a reachability check to confirm the player can walk to the required pushing position without crossing the box or walls. A visited set like (boxRow, boxCol, playerRow, playerCol) prevents revisiting states. This approach relies heavily on Breadth-First Search across a matrix grid to guarantee the minimum pushes.
Approach 2: A* Search for Optimal Pushes (O((mn)^2 log(mn)) time, O((mn)^2) space)
A* improves the search by guiding exploration toward the target using a heuristic. Each state still contains the box and player coordinates, but states are stored in a priority queue ordered by f = pushes + heuristic. A common heuristic is the Manhattan distance from the box to the target. This does not overestimate the required pushes, so the search remains optimal. Instead of expanding states purely level by level like BFS, A* prioritizes promising states and typically explores fewer configurations. The implementation uses a priority queue to efficiently select the next state with the smallest estimated cost.
Recommended for interviews: BFS with state tracking is the most common expected solution. It clearly models the puzzle as a graph search and guarantees the minimum number of pushes. Interviewers usually want to see correct state representation and reachability checks. Mentioning A* as an optimization shows deeper search algorithm knowledge and strong problem-solving maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with State Tracking | O((mn)^2) | O((mn)^2) | Standard solution for interviews. Guarantees minimum pushes and easier to reason about. |
| A* Search with Priority Queue | O((mn)^2 log(mn)) | O((mn)^2) | When optimizing search exploration. Heuristic reduces explored states in large grids. |