#1263

Hard

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Minimum Moves to Move a Box to Their Target Location

Solve the minimum moves to push a box to its target using BFS and priority handling in a grid-based warehouse layout efficiently.

array breadth first search heap priority queue matrix

Problem Statement

You are given an m x n grid representing a warehouse where a storekeeper can push a single box to a target location. Each cell is either a wall '#', empty floor '.', the player 'S', the box 'B', or the target 'T'. The player can move freely on empty floor cells and push the box if positioned directly adjacent and the next cell is free. Your goal is to determine the minimum number of pushes required to move the box to the target.

Movement rules enforce that the player can only push, not pull, the box. Pushing counts as one move, while walking around without pushing does not. The grid always contains exactly one player, one box, and one target. Walls block both the player and box, making pathfinding and careful state tracking essential. If reaching the target is impossible, return -1.

Examples

Example 1

Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]]

Output: 3

We return only the number of times the box is pushed.

Example 2

Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#","#","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]]

Output: -1

Example details omitted.

Example 3

Input: grid = [["#","#","#","#","#","#"], ["#","T",".",".","#","#"], ["#",".","#","B",".","#"], ["#",".",".",".",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]]

Output: 5

push the box down, left, left, up and up.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid contains only characters '.', '#', 'S', 'T', or 'B'.
There is only one character 'S', 'B', and 'T' in the grid.

Solution Approach

State Representation

Represent each search state as a tuple (player_row, player_col, box_row, box_col). This explicitly tracks both player and box positions and allows BFS to explore valid pushes and moves without revisiting identical configurations.

Breadth-First Search with Priority

Use BFS to explore all reachable positions, prioritizing states with fewer box pushes. For each state, check all four directions to see if the player can reach the position behind the box to push it forward, and enqueue resulting states if unvisited.

Visited States and Optimization

Maintain a visited set keyed by (box_row, box_col, player_row, player_col) to avoid cycles. For efficiency, only consider pushing actions that advance the box toward the target, pruning paths that cannot improve the current minimum number of pushes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of reachable states, which is O(m n m n) in the worst case, as each combination of player and box positions can be explored. Space complexity similarly depends on storing visited states and BFS queue, requiring O(m n m n) memory in the worst case.

What Interviewers Usually Probe

Expect clear state representation combining player and box positions.
Ask about BFS versus DFS trade-offs for minimizing box pushes.
Look for handling of unreachable states and pruning redundant paths.

Common Pitfalls or Variants

Common pitfalls

Confusing player movement with box pushes; only pushes count.
Not tracking visited states fully with both player and box positions, leading to infinite loops.
Failing to validate that the player can reach the push position before attempting a box push.

Follow-up variants

Multiple boxes and targets requiring multi-object BFS.
Adding weighted pushes where each push has a cost instead of uniform counting.
Larger grids with teleporters or moving obstacles affecting reachability.

FAQ

What is the best approach to solve Minimum Moves to Move a Box to Their Target Location?

Represent each state as (player_row, player_col, box_row, box_col) and use BFS with a priority queue to count minimal box pushes efficiently.

Do I need to count player moves without pushing?

No, only pushes count toward the move total; player walking without pushing does not increment the count.

Can the box be pulled instead of pushed?

No, the rules only allow pushing; your BFS must ensure the player is in position behind the box before pushing.

What data structures help avoid revisiting states?

Use a set or hash map keyed by both box and player positions to track visited states and prevent cycles.

How does the Array plus Breadth-First Search pattern apply here?

The grid is represented as a 2D array, and BFS systematically explores all reachable box pushes, optimizing with state tracking and priority.

terminal

Solution

Solution 1: Double-ended Queue + BFS

We consider the player's position and the box's position as a state, i.e., $(s_i, s_j, b_i, b_j)$, where $(s_i, s_j)$ is the player's position, and $(b_i, b_j)$ is the box's position. In the code implementation, we define a function $f(i, j)$, which maps the two-dimensional coordinates $(i, j)$ to a one-dimensional state number, i.e., $f(i, j) = i \times n + j$, where $n$ is the number of columns in the grid. So the player and the box's state is $(f(s_i, s_j), f(b_i, b_j))$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        def f(i: int, j: int) -> int:
            return i * n + j

        def check(i: int, j: int) -> bool:
            return 0 <= i < m and 0 <= j < n and grid[i][j] != "#"

        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == "S":
                    si, sj = i, j
                elif c == "B":
                    bi, bj = i, j
        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        q = deque([(f(si, sj), f(bi, bj), 0)])
        vis = [[False] * (m * n) for _ in range(m * n)]
        vis[f(si, sj)][f(bi, bj)] = True
        while q:
            s, b, d = q.popleft()
            bi, bj = b // n, b % n
            if grid[bi][bj] == "T":
                return d
            si, sj = s // n, s % n
            for a, b in pairwise(dirs):
                sx, sy = si + a, sj + b
                if not check(sx, sy):
                    continue
                if sx == bi and sy == bj:
                    bx, by = bi + a, bj + b
                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:
                        continue
                    vis[f(sx, sy)][f(bx, by)] = True
                    q.append((f(sx, sy), f(bx, by), d + 1))
                elif not vis[f(sx, sy)][f(bi, bj)]:
                    vis[f(sx, sy)][f(bi, bj)] = True
                    q.appendleft((f(sx, sy), f(bi, bj), d))
        return -1

Continue Practicing

#1368 minimum cost to make at least one valid path in a grid #1631 path with minimum effort #778 swim in rising water