1263. Minimum Moves to Move a Box to Their Target Location - Leetcode Solution

Code Implementation

from collections import deque

def minPushBox(grid):
    m, n = len(grid), len(grid[0])
    DIRS = [(-1,0),(1,0),(0,-1),(0,1)]

    # Find positions of box, target, and player
    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 in_bounds(x, y):
        return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'

    # BFS: (box_x, box_y, player_x, player_y)
    queue = deque()
    queue.append((box[0], box[1], player[0], player[1], 0))
    visited = set()
    visited.add((box[0], box[1], player[0], player[1]))

    def can_player_reach(sx, sy, tx, ty, box_x, box_y):
        # BFS to check if player can reach (tx,ty) from (sx,sy) without crossing box
        q = deque()
        q.append((sx, sy))
        seen = set()
        seen.add((sx, sy))
        while q:
            x, y = q.popleft()
            if (x, y) == (tx, ty):
                return True
            for dx, dy in DIRS:
                nx, ny = x + dx, y + dy
                if in_bounds(nx, ny) and (nx, ny) not in seen and (nx, ny) != (box_x, box_y):
                    seen.add((nx, ny))
                    q.append((nx, ny))
        return False

    while queue:
        bx, by, px, py, pushes = queue.popleft()
        if (bx, by) == target:
            return pushes
        for dx, dy in DIRS:
            nbx, nby = bx + dx, by + dy
            opx, opy = bx - dx, by - dy  # player must be here to push
            if in_bounds(nbx, nby) and in_bounds(opx, opy):
                if can_player_reach(px, py, opx, opy, bx, by):
                    state = (nbx, nby, bx, by)
                    if state not in visited:
                        visited.add(state)
                        queue.append((nbx, nby, bx, by, pushes + 1))
    return -1

#include <vector>
#include <queue>
#include <set>
using namespace std;

class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<pair<int,int>> DIRS{{-1,0},{1,0},{0,-1},{0,1}};
        pair<int,int> box, player, target;
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j) {
                if(grid[i][j]=='B') box={i,j};
                else if(grid[i][j]=='S') player={i,j};
                else if(grid[i][j]=='T') target={i,j};
            }
        auto in_bounds = [&](int x, int y){
            return x>=0 && x<m && y>=0 && y<n && grid[x][y]!='#';
        };
        struct State {
            int bx, by, px, py, pushes;
        };
        queue<State> q;
        set<tuple<int,int,int,int>> visited;
        q.push({box.first, box.second, player.first, player.second, 0});
        visited.insert({box.first, box.second, player.first, player.second});

        auto can_player_reach = [&](int sx, int sy, int tx, int ty, int bx, int by){
            queue<pair<int,int>> qq;
            set<pair<int,int>> seen;
            qq.push({sx,sy});
            seen.insert({sx,sy});
            while(!qq.empty()) {
                auto [x,y]=qq.front(); qq.pop();
                if(x==tx && y==ty) return true;
                for(auto [dx,dy]:DIRS) {
                    int nx=x+dx, ny=y+dy;
                    if(in_bounds(nx,ny) && seen.count({nx,ny})==0 && !(nx==bx && ny==by)) {
                        seen.insert({nx,ny});
                        qq.push({nx,ny});
                    }
                }
            }
            return false;
        };

        while(!q.empty()) {
            auto [bx,by,px,py,pushes] = q.front(); q.pop();
            if(bx==target.first && by==target.second) return pushes;
            for(auto [dx,dy]:DIRS) {
                int nbx=bx+dx, nby=by+dy;
                int opx=bx-dx, opy=by-dy;
                if(in_bounds(nbx,nby) && in_bounds(opx,opy)) {
                    if(can_player_reach(px,py,opx,opy,bx,by)) {
                        auto state = make_tuple(nbx,nby,bx,by);
                        if(visited.count(state)==0) {
                            visited.insert(state);
                            q.push({nbx,nby,bx,by,pushes+1});
                        }
                    }
                }
            }
        }
        return -1;
    }
};

import java.util.*;

class Solution {
    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] box = new int[2], player = new int[2], target = new int[2];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'B') { box[0]=i; box[1]=j; }
                else if (grid[i][j] == 'S') { player[0]=i; player[1]=j; }
                else if (grid[i][j] == 'T') { target[0]=i; target[1]=j; }
            }
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(new int[]{box[0], box[1], player[0], player[1], 0});
        visited.add(box[0]+","+box[1]+","+player[0]+","+player[1]);

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int bx=cur[0], by=cur[1], px=cur[2], py=cur[3], pushes=cur[4];
            if (bx == target[0] && by == target[1]) return pushes;
            for (int[] d : DIRS) {
                int nbx = bx + d[0], nby = by + d[1];
                int opx = bx - d[0], opy = by - d[1];
                if (inBounds(nbx, nby, m, n, grid) && inBounds(opx, opy, m, n, grid)) {
                    if (canPlayerReach(px, py, opx, opy, bx, by, grid)) {
                        String state = nbx+","+nby+","+bx+","+by;
                        if (!visited.contains(state)) {
                            visited.add(state);
                            queue.offer(new int[]{nbx, nby, bx, by, pushes+1});
                        }
                    }
                }
            }
        }
        return -1;
    }

    private boolean inBounds(int x, int y, int m, int n, char[][] grid) {
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
    }

    private boolean canPlayerReach(int sx, int sy, int tx, int ty, int bx, int by, char[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] seen = new boolean[m][n];
        q.offer(new int[]{sx, sy});
        seen[sx][sy] = true;
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (curr[0] == tx && curr[1] == ty) return true;
            for (int[] d : DIRS) {
                int nx = curr[0] + d[0], ny = curr[1] + d[1];
                if (inBounds(nx, ny, m, n, grid) && !seen[nx][ny] && (nx != bx || ny != by)) {
                    seen[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return false;
    }
}

/**
 * @param {character[][]} grid
 * @return {number}
 */
var minPushBox = function(grid) {
    const m = grid.length, n = grid[0].length;
    const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];
    let box, player, target;
    for(let i=0;i<m;i++)
        for(let j=0;j<n;j++) {
            if(grid[i][j]==='B') box=[i,j];
            else if(grid[i][j]==='S') player=[i,j];
            else if(grid[i][j]==='T') target=[i,j];
        }
    const inBounds = (x,y) => x>=0 && x<m && y>=0 && y<n && grid[x][y]!=='#';
    const canPlayerReach = (sx,sy,tx,ty,bx,by) => {
        const q = [[sx,sy]];
        const seen = Array.from({length:m},()=>Array(n).fill(false));
        seen[sx][sy]=true;
        while(q.length) {
            const [x,y]=q.shift();
            if(x===tx && y===ty) return true;
            for(const [dx,dy] of DIRS) {
                const nx=x+dx, ny=y+dy;
                if(inBounds(nx,ny) && !seen[nx][ny] && (nx!==bx||ny!==by)) {
                    seen[nx][ny]=true;
                    q.push([nx,ny]);
                }
            }
        }
        return false;
    };
    const queue = [[box[0],box[1],player[0],player[1],0]];
    const visited = new Set();
    visited.add(box[0]+','+box[1]+','+player[0]+','+player[1]);
    while(queue.length) {
        const [bx,by,px,py,pushes] = queue.shift();
        if(bx===target[0]&&by===target[1]) return pushes;
        for(const [dx,dy] of DIRS) {
            const nbx=bx+dx, nby=by+dy;
            const opx=bx-dx, opy=by-dy;
            if(inBounds(nbx,nby)&&inBounds(opx,opy)) {
                if(canPlayerReach(px,py,opx,opy,bx,by)) {
                    const state = nbx+','+nby+','+bx+','+by;
                    if(!visited.has(state)) {
                        visited.add(state);
                        queue.push([nbx,nby,bx,by,pushes+1]);
                    }
                }
            }
        }
    }
    return -1;
};

Problem Description

You are given a 2D grid representing a warehouse. The grid contains:

Walls ('#')
Empty cells ('.')
One box ('B')
One target location ('T')
One player ('S')

The player can move up, down, left, or right into empty cells (not through walls or the box). The player can push the box if they are adjacent to it and the cell on the opposite side of the box (in the direction of the push) is empty. The player cannot pull the box or push it diagonally.

The goal is to determine the minimum number of pushes required to move the box to the target location. If it is impossible, return -1.

Key constraints:

Only one box, one target, and one player exist on the grid.
The player can only push the box (not pull).
You must not revisit the same state (box and player positions) to avoid cycles.

Thought Process

At first glance, this problem may seem similar to a standard shortest-path search (like BFS), but with an added twist: the player must both navigate around obstacles and position themselves correctly to push the box.

A brute-force approach would attempt every possible sequence of moves, but this is inefficient because the number of possible states grows rapidly. Instead, we need to track both the box and player positions, and focus on pushes, since moving the player without pushing doesn't count towards the answer.

The conceptual shift is to treat each push as a state transition, and check if the player can reach the required position to make that push. This means that our BFS will be over states consisting of both the box's and the player's positions, not just the box's.

Solution Approach

To solve the problem efficiently, we use a BFS (Breadth-First Search) that tracks both the box and player positions. Here is the step-by-step approach:

State Representation:
- Each state is a tuple: (box_x, box_y, player_x, player_y)
- We also track the number of pushes so far.
BFS Queue:
- Initialize the queue with the starting positions of the box and the player, and zero pushes.
- Use a set to keep track of visited states to prevent cycles.
For Each State:
- For each of the four directions, consider pushing the box in that direction.
- To push, the player must be on the opposite side of the box (relative to the push direction).
- Check if the destination cell for the box is empty and within bounds.
- Check if the player can reach the required position (without crossing the box) using BFS.
Push and Queue:
- If all conditions are satisfied, enqueue the new state: the box moves, the player moves to the box's old position, and the push count increases by one.
Termination:
- If the box reaches the target, return the number of pushes.
- If the queue is empty and the box never reaches the target, return -1.

We use a hash set for visited states to ensure O(1) lookups and avoid revisiting the same configuration.

Example Walkthrough

Consider the following grid:

    [["#","#","#","#","#","#"],
     ["#","T","#","#","#","#"],
     ["#",".",".","B",".","#"],
     ["#",".","#","#",".","#"],
     ["#",".",".",".","S","#"],
     ["#","#","#","#","#","#"]]

The box starts at (2,3), the player at (4,4), and the target at (1,1).
Step 1: The player must first navigate to a position adjacent to the box and on the opposite side of the direction they wish to push.
Step 2: The player moves up and left (without pushing) to reach (2,2), which is to the left of the box.
Step 3: The player pushes the box right from (2,3) to (2,4), moving the player to (2,3).
Step 4: The player navigates around to push the box up, left, or right as needed, repeating the process: for each push, first check if the player can reach the required position.
This continues until the box is pushed onto the target at (1,1), or until all possibilities are exhausted.
The algorithm ensures the minimum number of pushes is found because BFS always explores the shallowest (fewest pushes) states first.

Time and Space Complexity

Brute-force Approach:

Would try all sequences of player moves and box pushes, leading to exponential time in the size of the grid.
Time Complexity: O(4^mn), where m and n are the grid dimensions.

Optimized BFS Approach:

Each state is a combination of box and player positions: O(m²n²).
For each state, we may perform a BFS to check if the player can reach the required position, which is O(mn).
Total Time Complexity: O(m³n³), since in the worst case, for each state, we do a BFS over the grid.
Space Complexity: O(m²n²) for the visited set and BFS queue.

The use of a visited set and careful state representation ensures that we do not revisit states, keeping the solution efficient for reasonable grid sizes.

Summary

The key insight is to model the problem as a BFS over states that include both the box and player positions, and to treat each push as a state transition. By checking whether the player can reach the required spot to push the box and using a visited set to avoid cycles, we ensure correctness and efficiency. This approach elegantly balances the complexity of the player's movement with the need to minimize box pushes, guaranteeing the minimum number of pushes is found.

AlgoMap.io

Want Help Cracking FAANG?