LeetCode 1263 - Minimum Moves to Move a Box to Their Target Location

LeetCode Problem 1263

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Heap (Priority Queue), Matrix

Solution

Problem Understanding

The problem is a variant of the classic "Sokoban" puzzle. You are given a grid representing a warehouse, where a player 'S' must push a box 'B' to a target location 'T'. The player can move in four directions on free floor tiles '.' but cannot walk through walls '#' or the box itself. The box can only be moved by the player pushing it from an adjacent cell, and each push counts toward the answer. The task is to compute the minimum number of pushes required to move the box to the target. If the box cannot reach the target due to walls or unreachable positions, return -1.

Inputs are guaranteed to have exactly one player, one box, and one target, which simplifies tracking positions. The grid size is constrained to m, n <= 20, which means a BFS-based search is feasible but a naive brute-force approach trying all player moves would be too slow due to the exponential state space.

Key observations include the fact that the player must be able to reach a cell behind the box to push it, so each potential box move is only valid if the player can access the corresponding cell. This introduces a two-level search: one for box positions and another to check player reachability.

Important edge cases include situations where the box is blocked by walls, the player is completely isolated from reaching behind the box, or the box is already on the target. These cases must return -1 or 0 appropriately.

Approaches

A brute-force approach would try every sequence of player moves and box pushes recursively, tracking all positions of the player and box. At each step, the algorithm would explore all four movement directions and check whether a push is possible. While this guarantees correctness, it is infeasible because the number of states grows as O((m*n)^2) for player-box combinations and exploring every movement sequence could lead to exponential runtime.

The optimal approach uses a BFS where the primary state is the box position and the player position, and transitions correspond to valid box pushes. Before pushing the box, we perform a secondary BFS (or DFS) to ensure the player can reach the required pushing position without crossing walls or the box itself. This allows pruning of invalid states early and ensures each state is visited at most once. Using BFS guarantees that the first time we reach the target box position is with the minimal number of pushes.

Algorithm Walkthrough

1. Locate initial positions: Scan the grid to find the coordinates of the player 'S', box 'B', and target 'T'.
2. Define BFS state: Represent each state as (box_x, box_y, player_x, player_y) and track the number of pushes made.
3. Queue initialization: Initialize a queue for BFS with the starting state and a visited set to prevent revisiting the same box-player configuration.
4. Direction vectors: Define four possible movement directions for pushing the box: up, down, left, right.
5. BFS traversal: While the queue is not empty, pop a state. For each direction, calculate the new box position if the box is pushed.
6. Check validity of push: Ensure the new box position is within bounds and is a free cell. Determine the cell behind the box (opposite the push) and check if the player can reach that cell using a BFS that avoids walls and the box itself.
7. State transition: If the push is valid and the resulting state has not been visited, add it to the queue with pushes + 1.
8. Check target: If the box reaches the target position, return the number of pushes.
9. Exhausted search: If BFS completes without reaching the target, return -1.

Why it works: BFS ensures that states are explored in order of increasing pushes. By only pushing when the player can actually reach the required position, we avoid invalid moves. The visited set guarantees that we never recompute states, ensuring efficiency.

Python Solution

from collections import deque
from typing import List, Tuple, Set

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        
        def in_bounds(x: int, y: int) -> bool:
            return 0 <= x < m and 0 <= y < n
        
        def can_player_reach(sx: int, sy: int, tx: int, ty: int, box: Tuple[int,int]) -> bool:
            """Check if player can reach (tx, ty) without crossing walls or the box."""
            visited = set()
            queue = deque([(sx, sy)])
            visited.add((sx, sy))
            while queue:
                x, y = queue.popleft()
                if (x, y) == (tx, ty):
                    return True
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if in_bounds(nx, ny) and (nx, ny) not in visited and grid[nx][ny] != '#' and (nx, ny) != box:
                        visited.add((nx, ny))
                        queue.append((nx, ny))
            return False
        
        # Locate player, box, and target
        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)
        
        queue = deque([(box, player, 0)]) # box_pos, player_pos, pushes
        visited: Set[Tuple[Tuple[int,int], Tuple[int,int]]] = set()
        visited.add((box, player))
        
        while queue:
            (bx, by), (px, py), pushes = queue.popleft()
            if (bx, by) == target:
                return pushes
            for dx, dy in directions:
                nbx, nby = bx + dx, by + dy
                px_required, py_required = bx - dx, by - dy
                if in_bounds(nbx, nby) and grid[nbx][nby] != '#' and in_bounds(px_required, py_required) and grid[px_required][py_required] != '#':
                    if can_player_reach(px, py, px_required, py_required, (bx, by)):
                        new_state = ((nbx, nby), (bx, by))
                        if new_state not in visited:
                            visited.add(new_state)
                            queue.append(((nbx, nby), (bx, by), pushes + 1))
        return -1

The Python implementation follows the algorithm closely. The can_player_reach function ensures the player can move behind the box before pushing. Each BFS iteration considers all four directions, updating the box and player positions and incrementing the push count only for valid moves.

Go Solution

package main

import "container/list"

func minPushBox(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    directions := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
    
    var player, box, target [2]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            switch grid[i][j] {
            case 'S':
                player = [2]int{i,j}
            case 'B':
                box = [2]int{i,j}
            case 'T':
                target = [2]int{i,j}
            }
        }
    }

    inBounds := func(x, y int) bool {
        return x >= 0 && x < m && y >= 0 && y < n
    }

    canPlayerReach := func(sx, sy, tx, ty int, boxPos [2]int) bool {
        visited := make(map[[2]int]bool)
        q := list.New()
        q.PushBack([2]int{sx, sy})
        visited[[2]int{sx, sy}] = true
        for q.Len() > 0 {
            e := q.Front()
            q.Remove(e)
            x, y := e.Value.([2]int)[0], e.Value.([2]int)[1]
            if x == tx && y == ty {
                return true
            }
            for _, d := range directions {
                nx, ny := x + d[0], y + d[1]
                if inBounds(nx, ny) && !visited[[2]int{nx, ny}] && grid[nx][ny] != '#' && !(nx == boxPos[0] && ny == boxPos[1]) {
                    visited[[2]int{nx, ny}] = true
                    q.PushBack([2]int{nx, ny})
                }
            }
        }
        return false
    }

    type State struct {
        box, player [2]int