Minimum Moves to Move a Box to Their Target Location

Problem Description

Welcome to the world of box pushing! Imagine you’re a player in a game, and your sole purpose in life is to push a box to a target location. Sounds easy, right? Well, not so fast! You have to navigate through walls, avoid getting stuck, and make sure the box doesn’t roll away into the abyss.

In this delightful little puzzle, you are given a grid representing a room where:

# represents walls,
. represents empty spaces,
B represents the box,
S represents your starting position,
T represents the target position.

Your mission, should you choose to accept it, is to determine the minimum number of moves required to push the box to the target location. And just to spice things up, you can only push the box, not pull it. So, if you’ve ever tried to move a stubborn piece of furniture, you’ll know the struggle!

Code Solution


class Solution:
    def minPushBox(self, grid: list[list[str]]) -> int:
        dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
        m = len(grid)
        n = len(grid[0])

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    box = (i, j)
                elif grid[i][j] == 'S':
                    player = (i, j)
                elif grid[i][j] == 'T':
                    target = (i, j)

        def isInvalid(playerX: int, playerY: int) -> bool:
            return (playerX < 0 or playerX == m or playerY < 0 or playerY == n or
                    grid[playerX][playerY] == '#')

        def canGoTo(playerX: int, playerY: int, fromX: int, fromY: int, boxX: int, boxY: int) -> bool:
            q = collections.deque([(playerX, playerY)])
            seen = {(playerX, playerY)}

            while q:
                i, j = q.popleft()
                if i == fromX and j == fromY:
                    return True
                for dx, dy in dirs:
                    x = i + dx
                    y = j + dy
                    if isInvalid(x, y):
                        continue
                    if (x, y) in seen:
                        continue
                    if x == boxX and y == boxY:
                        continue
                    q.append((x, y))
                    seen.add((x, y))

            return False

        q = collections.deque([(box[0], box[1], player[0], player[1])])
        seen = {(box[0], box[1], player[0], player[1])}

        step = 0
        while q:
            for _ in range(len(q)):
                boxX, boxY, playerX, playerY = q.popleft()
                if boxX == target[0] and boxY == target[1]:
                    return step
                for k, (dx, dy) in enumerate(dirs):
                    nextBoxX = boxX + dx
                    nextBoxY = boxY + dy
                    if isInvalid(nextBoxX, nextBoxY):
                        continue
                    if (nextBoxX, nextBoxY, boxX, boxY) in seen:
                        continue
                    fromX = boxX + dirs[(k + 2) % 4][0]
                    fromY = boxY + dirs[(k + 2) % 4][1]
                    if isInvalid(fromX, fromY):
                        continue
                    if canGoTo(playerX, playerY, fromX, fromY, boxX, boxY):
                        q.append((nextBoxX, nextBoxY, boxX, boxY))
                        seen.add((nextBoxX, nextBoxY, boxX, boxY))
            step += 1

        return -1

Approach Explanation

The code uses a breadth-first search (BFS) approach to explore all possible moves. It keeps track of the box’s position and the player’s position, checking if the player can reach the box before pushing it. The BFS ensures that we explore the shortest path to the target, incrementing the step count each time we push the box.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(m * n * (m + n)), where m is the number of rows and n is the number of columns in the grid.
Space Complexity	O(m * n), which is used for the queue and the visited set to keep track of the states we have already explored.

Real-World Example

Imagine you’re at a party, and there’s a giant box of pizza that everyone wants to get to. You’re the designated pizza pusher, and you have to navigate through a maze of people (walls) to get the pizza to the hungry crowd (target). Just like in the problem, you can only push the box forward, and if you get stuck, well, good luck getting that pizza to the party!