LeetCode Solutions Blog

Minimum Moves to Move a Box to Their Target Location

Difficulty: Hard

Problem Description

A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations. The task is to move the box 'B' to the target position 'T' under certain rules regarding walls, floors, and the player's movements. Return the minimum number of pushes needed to move the box to the target, or -1 if it's impossible.

Key Insights

The problem can be modeled as a search problem in a constrained environment (the grid).
The player must navigate around walls and other obstacles while pushing the box.
The BFS (Breadth-First Search) algorithm is suitable for finding the shortest path in an unweighted grid.
The state space can be represented by the box's position and the player's position.

Space and Time 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, considering all possible positions for the box and the player.

Space Complexity: O(m * n), required for the visited states and the queue in the BFS.

Solution

The solution involves using Breadth-First Search (BFS) to explore the state space of the grid. Each state consists of the box's position and the player's position. The BFS will explore all possible moves, counting the number of pushes required to move the box to the target. The algorithm maintains a queue of states to explore and a set of visited states to avoid cycles. When the box reaches the target position, the count of pushes is returned.

Code Solutions

from collections import deque

def minPushBox(grid):
    m, n = len(grid), len(grid[0])
    
    # Find positions of S, B, and T
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 'S':
                player = (i, j)
            elif grid[i][j] == 'B':
                box = (i, j)
            elif grid[i][j] == 'T':
                target = (i, j)
    
    # Directions for moving (up, down, left, right)
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def canMove(px, py, bx, by, direction):
        # Calculate new box position
        bx_new, by_new = bx + direction[0], by + direction[1]
        # Check if the new box position is valid
        if not (0 <= bx_new < m and 0 <= by_new < n) or grid[bx_new][by_new] == '#':
            return False
        # Check if the player can reach the new box position
        return bfs(px, py, bx, by, bx_new, by_new)
    
    def bfs(px, py, bx, by, tx, ty):
        queue = deque([(px, py)])
        visited = set()
        visited.add((px, py))
        
        while queue:
            x, y = queue.popleft()
            if (x, y) == (tx, ty):
                return True
            
            for direction in directions:
                nx, ny = x + direction[0], y + direction[1]
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != '#':
                    if (nx, ny) != (bx, by) and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        queue.append((nx, ny))
        
        return False
    
    queue = deque([(box[0], box[1], player[0], player[1], 0)])  # (bx, by, px, py, pushes)
    visited = set()
    visited.add((box[0], box[1], player[0], player[1]))
    
    while queue:
        bx, by, px, py, pushes = queue.popleft()
        
        if (bx, by) == target:
            return pushes
        
        for direction in directions:
            # New box position
            new_bx, new_by = bx + direction[0], by + direction[1]
            # Check if box can be moved
            if canMove(px, py, bx, by, direction):
                # New player position is the current box position
                new_px, new_py = bx, by
                state = (new_bx, new_by, bx, by)
                if state not in visited:
                    visited.add(state)
                    queue.append((new_bx, new_by, new_px, new_py, pushes + 1))
    
    return -1