LeetCode Solutions Blog

Minimum Moves to Move a Box to Their Target Location

Number: 1389

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an m x n grid representing a warehouse, the grid contains walls ('#'), floors ('.'), one box ('B'), one target ('T'), and one player ('S'). The goal is to determine the minimum number of pushes needed to move the box to the target cell. The player can move freely on floors but cannot pass through walls or the box. A push is only valid if the player can reach the required position behind the box (opposite the push direction) without moving the box. Return -1 if the target cannot be reached.

Key Insights

The problem involves two layers of search: one to push the box and another to validate the player’s path.
States are defined by both the box’s and the player's positions.
A BFS is used to guarantee that the first time the box reaches the target, it is done with the minimum number of pushes.
Before every push, perform a secondary BFS to check if the player can reach the required position to push the box.
Maintain a visited set to avoid re-exploring the same (box, player) state.

Space and Time Complexity

Time Complexity: O(M * N * M * N) in the worst-case scenario due to exploring states in an m x n grid. Space Complexity: O(M * N * M * N) for storing visited states.

Solution

We solve the problem using a double BFS approach. The outer BFS explores states defined by the box and player positions along with the count of pushes. For each potential push direction, we check if the destination for the box is valid and if the player can reach the necessary spot behind the box using a helper BFS. This layered check ensures that every push is valid per game rules. We use a queue to manage the BFS and a set to remember visited states.

Code Solutions

from collections import deque

def minPushBox(grid):
    m, n = len(grid), len(grid[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Locate initial positions of player, box, and target
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 'S':
                player_start = (i, j)
            elif grid[i][j] == 'B':
                box_start = (i, j)
            elif grid[i][j] == 'T':
                target = (i, j)
    
    # BFS queue with state: (push_count, box_row, box_col, player_row, player_col)
    queue = deque()
    queue.append((0, box_start[0], box_start[1], player_start[0], player_start[1]))
    visited = set()
    visited.add((box_start, player_start))
    
    # Check if the player can reach destination (dest_r, dest_c) from (pr, pc) without crossing walls or box.
    def canReach(pr, pc, dest_r, dest_c, b_r, b_c):
        q = deque([(pr, pc)])
        seen = {(pr, pc)}
        while q:
            r, c = q.popleft()
            if (r, c) == (dest_r, dest_c):
                return True
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen and grid[nr][nc] != '#' and (nr, nc) != (b_r, b_c):
                    seen.add((nr, nc))
                    q.append((nr, nc))
        return False

    while queue:
        pushes, box_r, box_c, player_r, player_c = queue.popleft()
        if (box_r, box_c) == target:
            return pushes
        for dr, dc in directions:
            new_box_r, new_box_c = box_r + dr, box_c + dc
            req_player_r, req_player_c = box_r - dr, box_c - dc
            
            if not (0 <= new_box_r < m and 0 <= new_box_c < n and grid[new_box_r][new_box_c] != '#'):
                continue
            if not (0 <= req_player_r < m and 0 <= req_player_c < n and grid[req_player_r][req_player_c] != '#'):
                continue
            if not canReach(player_r, player_c, req_player_r, req_player_c, box_r, box_c):
                continue
            
            new_state = ((new_box_r, new_box_c), (box_r, box_c))
            if new_state in visited:
                continue
            visited.add(new_state)
            queue.append((pushes + 1, new_box_r, new_box_c, box_r, box_c))
    return -1

# Example usage:
grid = ["######",
        "#T####",
        "#..B.#",
        "#.##.#",
        "#..S.#",
        "######"]
print(minPushBox(grid))