HardBreadth-First SearchGraphMatrix

Minimum Moves to Move a Box to Their Target Location

1 approach, code in every language

You are given a grid where each cell is floor ('.'), a wall ('#'), the player's starting cell ('S'), the box ('B'), or the target cell ('T'). The player wants to push the single box onto the target.

The player walks one step at a time in the four cardinal directions onto floor cells. To push the box, the player must stand directly on the side opposite the push direction and step into the box, which shifts the box one cell forward; that destination cell must be floor. Each push counts as one move while walking is free. Return the minimum number of pushes to get the box onto the target, or -1 if it cannot be done.

Example 1

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

Output: 3

The player maneuvers around the box and pushes it three times to land it on the target.

Example 2

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

Output: -1

A wall row blocks the player from ever standing below the box to push it up toward the target.

Constraints

m == grid.length and n == grid[i].length
1 ≤ m, n ≤ 20
The grid contains exactly one 'S', one 'B', and one 'T'
Every cell is one of '.', '#', 'S', 'B', 'T'

0-1 BFS over (box, player) states

Search combined box-and-player states where walking the player costs 0 and each box push costs 1.

Loading animation…

Intuition

We only want to minimize box pushes, and the player's walking between pushes is free, so this is a shortest-path search with two edge weights: zero for a player step and one for a push. Running a 0-1 BFS (front of the deque for free walks, back for pushes) over states that combine the box position with the player position finds the fewest pushes. Tracking the player's location matters because whether a given push is even possible depends on where the player can stand.

Algorithm walkthrough

1Scan the grid once to record the starting cells of the box, the player, and the target.
2Represent each state as the pair (box cell, player cell); begin from the initial pair with a push count of 0.
3Pull the cheapest state from a deque. For every direction the player can step onto a free neighbor, add that walk state to the front with the same cost.
4If the player's step lands on the box's cell and the cell beyond the box is free, that is a push: the box shifts, the player takes the box's old cell, and the new state goes to the back with cost + 1.
5The moment the box occupies the target, return its push count; if the deque drains without reaching it, return -1.

Implementation

from collections import deque
from typing import List

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        box = player = target = (0, 0)
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 'B':
                    box = (r, c)
                elif grid[r][c] == 'S':
                    player = (r, c)
                elif grid[r][c] == 'T':
                    target = (r, c)

        def free(r, c):
            return 0 <= r < rows and 0 <= c < cols and grid[r][c] != '#'

        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        start = (box[0], box[1], player[0], player[1])
        dist = {start: 0}
        dq = deque([start])
        while dq:
            br, bc, pr, pc = dq.popleft()
            d = dist[(br, bc, pr, pc)]
            if (br, bc) == target:
                return d
            for dr, dc in dirs:
                nr, nc = pr + dr, pc + dc
                if not free(nr, nc):
                    continue
                if (nr, nc) == (br, bc):
                    nbr, nbc = br + dr, bc + dc
                    if not free(nbr, nbc):
                        continue
                    state = (nbr, nbc, nr, nc)
                    if state not in dist or dist[state] > d + 1:
                        dist[state] = d + 1
                        dq.append(state)
                else:
                    state = (br, bc, nr, nc)
                    if state not in dist or dist[state] > d:
                        dist[state] = d
                        dq.appendleft(state)
        return -1

Time

O((m * n)^2)

Space

O((m * n)^2)

There are up to (m*n) box cells times (m*n) player cells combined states, each expanded a constant number of times.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free