1263. Minimum Moves to Move a Box to Their Target Location

HardBreadth-First SearchArrayMatrixHeap (Priority Queue)

Problem Description

The problem at hand is a puzzle inspired by the 'Sokoban' game, where the goal is to move objects (in this case a single box ‘B’) to a specified destination ('T') within a constrained environment. The game is played on a grid that includes walls ('#'), empty floor cells ('.'), the box ('B'), and the target ('T'). The player is represented by ('S') and can only move on empty floor cells, but cannot pass through walls or the box. However, the player can move the box to an adjacent free cell by pushing it from the side. Each push moves the box one cell in the desired direction. The task is to determine the minimum number of pushes required to get the box to the target. If this isn't possible, the function should return -1.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: Although the environment is a grid, this scenario of moving objects within a grid can be conceptualized as a graph where each cell is a node and edges represent possible movements between cells.

Is it a tree?

No: The graph contains many possible paths to reach the target, not just a single path from a root, which excludes it from being a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: In this problem, the player can move around freely, meaning cycles can exist (e.g., moving in a circle), so it's not acyclic.

Is the problem related to shortest paths?

Yes: The goal is to find the minimum number of moves to move a box to a target location, which can be framed as finding the shortest path in a graph.

Is the graph weighted?

No: Each move from one cell to another can be considered as having the same cost or weight, either it's valid or not, meaning the graph can be seen as unweighted.

Conclusion: The flowchart suggests using BFS for this shortest-path problem in an unweighted graph, where each step (i.e., move) is considered with equal weight. BFS is well-suited for exploring all possible positions level by level to find the minimum number of moves required.

Intuition

To resolve this problem, we rely on Breadth-First Search (BFS) to explore the warehouse grid systematically. BFS is a fitting choice as it explores all possible moves from a given position before moving on to moves further away, ensuring that the number of pushes is kept to a minimum.

The BFS algorithm is applied with the following considerations:

The state in the BFS includes both the current position of the player and the position of the box. This is because the player's position relative to the box is crucial to determine whether a push is possible.
We use a queue to maintain the states, and each state includes the current position of the player, the box, and the number of pushes so far.
The solution uses a function (f) to convert a 2D grid coordinate into a unique number in a 1D array. This is helpful to track visited states and prevents revisiting the same state, which is essential to avoid infinite loops and reduce computation.
The check function ensures that the moves are within the bounds of the grid and not into walls.
For each valid player move, we then check if that move results in pushing the box. If so, we update the box's position and increment the push count.
As we are interested in reaching the target with the minimum pushes, we explore player moves that do not result in a push by adding them to the front of the queue. This prioritizes exploration of the space without using extra pushes.
To handle the visited states, a 2D visited array is used (where each entry corresponds to a unique combination of player and box positions) to avoid revisiting the same state.
Lastly, when the box reaches the target, the current count of pushes is returned, as that represents the minimum pushes required.

Implementing these approaches results in a function that can reliably determine the minimum number of pushes needed to move the box to the target or decide if the task is impossible.

Learn more about Breadth-First Search and Heap (Priority Queue) patterns.

Solution Approach

The solution approach involves a breadth-first search (BFS) algorithm to explore the grid step by step.

We start by initializing a queue q that holds tuples containing the encoded positions of the player s, the box b, and the number of pushes d performed so far.
A check function ensures that a move is valid—meaning that it's within the boundaries of the grid and not walking into walls.
The code iterates over the grid, locating the starting positions of the player S and the box B.
An embedded helper function f(i, j) simplifies position encoding by converting 2D coordinates (i, j) into a single integer, allowing us to track positions easily.
A 2D boolean array vis is created to represent each unique state combination of player and box positions to keep track of whether a state has been visited.
BFS commences by dequeuing from q. If the box position corresponds to the target position T, the function returns the current number of pushes d.
Otherwise, for each dequeued state, the function explores all possible player moves. If the move positions the player adjacent to the box, it simulates a push by moving the box to the next cell.
If pushing the box is possible (i.e., the next cell in the direction of the push is free), we enqueue that new state with one additional push to the queue.
On the other hand, any move where the player is free to move without pushing the box is considered first, by adding it to the front of the queue. This ensures we try all possible player moves before pushes, optimizing the number of pushes used.
The BFS continues until the queue is depleted or the target is reached, resulting in the function returning the number of pushes d. If the queue is depleted and the target was never reached, the function returns -1, signaling that it's impossible to push the box to the target.

This approach systematically explores the grid, keeping track of the minimum pushes needed at every step, ensuring the solution is both correct and optimized in terms of the number of moves made.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

The warehouse grid looks like this:

####
#S.#
#B.#
#T.#
####

Using the approach outlined, let's walk through a possible BFS.

Initialize the queue with the starting position of the player S and the box B as well as the push count of 0. Let's represent this state as ((1, 1), (2, 1), 0) for (S position, B position, pushes). We can encode these positions using our helper function f(i, j), but for simplicity, we'll keep the 2D coordinates for this example.
Our 2D vis array starts as all False and we mark the starting state as visited.
We examine the queue, which initially only contains our starting state. Since the box isn't at the target, we'll consider moves for the player.
The player has 3 possible moves: up, left, and right (down would move into the box, which is not allowed unless the box can be pushed). None of these moves results in pushing the box, so each valid player move is added to the front of the queue with push count still at 0.
We take the right move for the player: the player moves to (1, 2), so now the player is next to the box. We enqueue this with the box still at (2, 1) and push count still at 0.
Now, the player is in a position to push the box. Since moving down from (1, 2) will position the player at (2, 2) and push the box to (3, 1), we check if this is valid. The box being moved down to (3, 1) is valid because the cell is free.
The new state ((2, 2), (3, 1), 1) represents the player having pushed the box once. This state is enqueued with push count updated to 1, and the vis array is updated to mark this state as visited.
Next, we dequeue the new state and check for player moves. The player can move up, but it won’t change the box position. Moving down now will push the box to the target (4, 1), so the new state will be ((3, 1), (4, 1), 2). This move is valid and results in another push.
Since the box has now reached the target, the BFS completes, and the total count of pushes 2 is returned as the solution.

This example walkthrough represents a simple scenario where the BFS algorithm successfully finds the minimum number of pushes needed to get the box to the target. In more complex scenarios, the BFS would continue exploring different states until the solution is found or deemed impossible.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def minPushBox(self, grid: List[List[str]]) -> int:
5      
6        # Helper function to flatten the 2D grid coordinates into 1D.
7        def get_flat_index(row: int, col: int) -> int:
8            return row * cols + col
9
10        # Check if the position (i, j) is within the grid and not an obstacle.
11        def is_valid(row: int, col: int) -> bool:
12            return 0 <= row < rows and 0 <= col < cols and grid[row][col] != "#"
13
14        # Find the starting positions of the Player (S) and the Box (B).
15        for i, row in enumerate(grid):
16            for j, cell in enumerate(row):
17                if cell == "S":
18                    start_row, start_col = i, j
19                elif cell == "B":
20                    box_row, box_col = i, j
21
22        # Dimensions of the grid
23        rows, cols = len(grid), len(grid[0])
24
25        # Possible 4 directions (up, right, down, left) as delta coordinates.
26        directions = (-1, 0, 1, 0, -1)
27
28        # Initialize the queue with the starting position of the player and box, with a move distance of 0.
29        queue = deque([(get_flat_index(start_row, start_col), get_flat_index(box_row, box_col), 0)])
30
31        # Visited positions: Visited states are represented by player and box positions.
32        visited = [[False] * (rows * cols) for _ in range(rows * cols)]
33        visited[get_flat_index(start_row, start_col)][get_flat_index(box_row, box_col)] = True
34
35        while queue:
36            player, box, distance = queue.popleft()
37            box_row, box_col = box // cols, box % cols
38
39            # If the current box position is the target, return the distance.
40            if grid[box_row][box_col] == "T":
41                return distance
42
43            player_row, player_col = player // cols, player % cols
44
45            # Iterate over all possible moves.
46            for delta_row, delta_col in zip(directions, directions[1:]):
47                next_player_row, next_player_col = player_row + delta_row, player_col + delta_col
48
49                # Check if the next player position is valid.
50                if not is_valid(next_player_row, next_player_col):
51                    continue
52              
53                # The player moves the box if they are adjacent.
54                if next_player_row == box_row and next_player_col == box_col:
55                    next_box_row, next_box_col = box_row + delta_row, box_col + delta_col
56                  
57                    # Check if the new box position is valid and has not been visited.
58                    if not is_valid(next_box_row, next_box_col) or visited[get_flat_index(next_player_row, next_player_col)][get_flat_index(next_box_row, next_box_col)]:
59                        continue
60
61                    # Update visited and add the new state to the queue.
62                    visited[get_flat_index(next_player_row, next_player_col)][get_flat_index(next_box_row, next_box_col)] = True
63                    queue.append((get_flat_index(next_player_row, next_player_col), get_flat_index(next_box_row, next_box_col), distance + 1))
64              
65                # If the player is not pushing the box, we add the new state to the front of the queue to check it sooner.
66                elif not visited[get_flat_index(next_player_row, next_player_col)][get_flat_index(box_row, box_col)]:
67                    visited[get_flat_index(next_player_row, next_player_col)][get_flat_index(box_row, box_col)] = True
68                    queue.appendleft((get_flat_index(next_player_row, next_player_col), get_flat_index(box_row, box_col), distance))
69
70        # Return -1 if it's impossible to push the box to the target.
71        return -1
72

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    private int numRows;        // Number of rows in the grid
6    private int numCols;        // Number of columns in the grid
7    private char[][] grid;      // The provided grid
8
9    public int minPushBox(char[][] grid) {
10        numRows = grid.length;
11        numCols = grid[0].length;
12        this.grid = grid;
13        int startIndex = 0, startJIndex = 0, boxIIndex = 0, boxJIndex = 0;
14
15        // Locate the starting position and the box's position
16        for (int i = 0; i < numRows; ++i) {
17            for (int j = 0; j < numCols; ++j) {
18                if (grid[i][j] == 'S') {
19                    startIndex = i;
20                    startJIndex = j;
21                } else if (grid[i][j] == 'B') {
22                    boxIIndex = i;
23                    boxJIndex = j;
24                }
25            }
26        }
27
28        // Set up directions for up, right, down, left
29        int[] directions = {-1, 0, 1, 0, -1};
30        Deque<int[]> queue = new ArrayDeque<>();
31        boolean[][] visited = new boolean[numRows * numCols][numRows * numCols];
32        queue.offer(new int[] {flattenCoordinates(startIndex, startJIndex), flattenCoordinates(boxIIndex, boxJIndex), 0});
33        visited[flattenCoordinates(startIndex, startJIndex)][flattenCoordinates(boxIIndex, boxJIndex)] = true;
34
35        // Breadth-first search
36        while (!queue.isEmpty()) {
37            int[] position = queue.poll();
38            int pushes = position[2];
39            boxIIndex = position[1] / numCols;
40            boxJIndex = position[1] % numCols;
41
42            // Check if the box is at the target position
43            if (grid[boxIIndex][boxJIndex] == 'T') {
44                return pushes;
45            }
46
47            startIndex = position[0] / numCols;
48            startJIndex = position[0] % numCols;
49
50            // Explore all possible movements
51            for (int k = 0; k < 4; ++k) {
52                int nextStartI = startIndex + directions[k];
53                int nextStartJ = startJIndex + directions[k + 1];
54
55                if (!isValidPosition(nextStartI, nextStartJ)) {
56                    continue;
57                }
58
59                // Move the player and/or box
60                if (nextStartI == boxIIndex && nextStartJ == boxJIndex) {
61                    int nextBoxI = boxIIndex + directions[k];
62                    int nextBoxJ = boxJIndex + directions[k + 1];
63                    if (!isValidPosition(nextBoxI, nextBoxJ) || visited[flattenCoordinates(nextStartI, nextStartJ)][flattenCoordinates(nextBoxI, nextBoxJ)]) {
64                        continue;
65                    }
66                    visited[flattenCoordinates(nextStartI, nextStartJ)][flattenCoordinates(nextBoxI, nextBoxJ)] = true;
67                    queue.offer(new int[] {flattenCoordinates(nextStartI, nextStartJ), flattenCoordinates(nextBoxI, nextBoxJ), pushes + 1});
68                } else if (!visited[flattenCoordinates(nextStartI, nextStartJ)][flattenCoordinates(boxIIndex, boxJIndex)]) {
69                    visited[flattenCoordinates(nextStartI, nextStartJ)][flattenCoordinates(boxIIndex, boxJIndex)] = true;
70                    queue.offerFirst(new int[] {flattenCoordinates(nextStartI, nextStartJ), flattenCoordinates(boxIIndex, boxJIndex), pushes});
71                }
72            }
73        }
74        // If the target can't be reached, return -1
75        return -1;
76    }
77
78    // Convert 2D coordinates into a single integer for mapping purposes
79    private int flattenCoordinates(int i, int j) {
80        return i * numCols + j;
81    }
82
83    // Check if the given coordinates are within bounds and not blocked by an obstacle
84    private boolean isValidPosition(int i, int j) {
85        return i >= 0 && i < numRows && j >= 0 && j < numCols && grid[i][j] != '#';
86    }
87}
88

1#include <vector>
2#include <deque>
3#include <tuple>
4#include <cstring>
5
6using namespace std;
7
8class Solution {
9public:
10    // Function to find the minimum number of pushes to move the box to the target location
11    int minPushBox(vector<vector<char>>& grid) {
12        int rowCount = grid.size(), colCount = grid[0].size(); // Store grid dimensions
13        // Initialize variables to store the starting positions of the player (S) and the box (B)
14        int playerRow, playerCol, boxRow, boxCol;
15
16        // Find the initial positions for the player and the box
17        for (int row = 0; row < rowCount; ++row) {
18            for (int col = 0; col < colCount; ++col) {
19                if (grid[row][col] == 'S') {
20                    playerRow = row, playerCol = col;
21                } else if (grid[row][col] == 'B') {
22                    boxRow = row, boxCol = col;
23                }
24            }
25        }
26
27        // Lambda function to convert 2D coordinates to 1D
28        auto to1D = [&](int row, int col) {
29            return row * colCount + col;
30        };
31
32        // Lambda function to check if a cell is within bounds and not blocked
33        auto isValid = [&](int row, int col) {
34            return row >= 0 && row < rowCount && col >= 0 && col < colCount && grid[row][col] != '#';
35        };
36
37        // Array for directions (up, right, down, and left)
38        int directions[5] = {-1, 0, 1, 0, -1};
39
40        // Queue to perform BFS, tuple contains 1D positions for player, box and number of pushes
41        deque<tuple<int, int, int>> bfsQueue;
42        bfsQueue.emplace_back(to1D(playerRow, playerCol), to1D(boxRow, boxCol), 0);
43
44        // Visited array to keep track of visited states, use 1D coordinates
45        bool visited[rowCount * colCount][rowCount * colCount];
46        memset(visited, false, sizeof(visited));
47        visited[to1D(playerRow, playerCol)][to1D(boxRow, boxCol)] = true;
48      
49        // Perform BFS
50        while (!bfsQueue.empty()) {
51            auto [playerPos, boxPos, distance] = bfsQueue.front();
52            bfsQueue.pop_front();
53            playerRow = playerPos / colCount, playerCol = playerPos % colCount;
54            boxRow = boxPos / colCount, boxCol = boxPos % colCount;
55          
56            // If the box is at the target location, return the number of pushes
57            if (grid[boxRow][boxCol] == 'T') {
58                return distance;
59            }
60
61            // Explore neighboring cells
62            for (int k = 0; k < 4; ++k) {
63                int nextPlayerRow = playerRow + directions[k], nextPlayerCol = playerCol + directions[k + 1];
64                if (!isValid(nextPlayerRow, nextPlayerCol)) { // Next position for player must be valid
65                    continue;
66                }
67                if (nextPlayerRow == boxRow && nextPlayerCol == boxCol) { // Player is pushing the box
68                    int nextBoxRow = boxRow + directions[k], nextBoxCol = boxCol + directions[k + 1];
69                    // Next position for the box must be valid and not visited
70                    if (!isValid(nextBoxRow, nextBoxCol) || visited[to1D(nextPlayerRow, nextPlayerCol)][to1D(nextBoxRow, nextBoxCol)]) {
71                        continue;
72                    }
73                    visited[to1D(nextPlayerRow, nextPlayerCol)][to1D(nextBoxRow, nextBoxCol)] = true;
74                    bfsQueue.emplace_back(to1D(nextPlayerRow, nextPlayerCol), to1D(nextBoxRow, nextBoxCol), distance + 1);
75                } else if (!visited[to1D(nextPlayerRow, nextPlayerCol)][to1D(boxRow, boxCol)]) { // Player moves without pushing the box
76                    visited[to1D(nextPlayerRow, nextPlayerCol)][to1D(boxRow, boxCol)] = true;
77                    bfsQueue.emplace_front(to1D(nextPlayerRow, nextPlayerCol), to1D(boxRow, boxCol), distance);
78                }
79            }
80        }
81        return -1; // If unable to reach the target, return -1
82    }
83};
84

1// Global variables for the grid dimensions
2let gridRows: number;
3let gridCols: number;
4
5// Helper function to convert 2D coordinates to a unique identifier
6function getFlatIndex(row: number, col: number): number {
7    return row * gridCols + col;
8}
9
10// Helper function to check if given coordinates are inside the grid and not an obstacle
11function isCellFree(row: number, col: number, grid: string[][]): boolean {
12    return row >= 0 && row < gridRows && col >= 0 && col < gridCols && grid[row][col] !== '#';
13}
14
15// Main function to calculate the minimum number of pushes to move the box to the target
16function minPushBox(grid: string[][]): number {
17    gridRows = grid.length;
18    gridCols = grid[0].length;
19    let startRow = 0, startCol = 0, boxRow = 0, boxCol = 0;
20
21    // Find the starting position of the player ('S') and the box ('B')
22    for (let i = 0; i < gridRows; ++i) {
23        for (let j = 0; j < gridCols; ++j) {
24            if (grid[i][j] === 'S') {
25                [startRow, startCol] = [i, j];
26            } else if (grid[i][j] === 'B') {
27                [boxRow, boxCol] = [i, j];
28            }
29        }
30    }
31
32    // Prepare the BFS queue and visited check
33    const queue: [number, number, number][] = [];
34    const visited = Array.from({ length: gridRows * gridCols }, () => Array(gridRows * gridCols).fill(false));
35
36    // Start BFS with the starting positions of player and box
37    queue.push([getFlatIndex(startRow, startCol), getFlatIndex(boxRow, boxCol), 0]);
38    visited[getFlatIndex(startRow, startCol)][getFlatIndex(boxRow, boxCol)] = true;
39
40    // Define possible move directions
41    const directions = [-1, 0, 1, 0, -1];
42
43    // Perform BFS to find the minimum distance
44    while (queue.length > 0) {
45        const [currentPlayer, currentBox, distance] = queue.shift()!;
46        const [playerRow, playerCol] = [Math.floor(currentPlayer / gridCols), currentPlayer % gridCols];
47        const [boxRow, boxCol] = [Math.floor(currentBox / gridCols), currentBox % gridCols];
48      
49        // If the box is on the target, return the current distance
50        if (grid[boxRow][boxCol] === 'T') {
51            return distance;
52        }
53
54        // Check all possible directions to move
55        for (let k = 0; k < 4; ++k) {
56            const [nextPlayerRow, nextPlayerCol] = [playerRow + directions[k], playerCol + directions[k + 1]];
57          
58            // Skip if the next player position is invalid
59            if (!isCellFree(nextPlayerRow, nextPlayerCol, grid)) {
60                continue;
61            }
62
63            // If the player moves to the position of the box, simulate pushing the box
64            if (nextPlayerRow === boxRow && nextPlayerCol === boxCol) {
65                const [nextBoxRow, nextBoxCol] = [boxRow + directions[k], boxCol + directions[k + 1]];
66                if (!isCellFree(nextBoxRow, nextBoxCol, grid) || visited[getFlatIndex(nextPlayerRow, nextPlayerCol)][getFlatIndex(nextBoxRow, nextBoxCol)]) {
67                    continue;
68                }
69                // Mark the new positions as visited
70                visited[getFlatIndex(nextPlayerRow, nextPlayerCol)][getFlatIndex(nextBoxRow, nextBoxCol)] = true;
71                // Add new positions to the queue with distance incremented
72                queue.push([getFlatIndex(nextPlayerRow, nextPlayerCol), getFlatIndex(nextBoxRow, nextBoxCol), distance + 1]);
73            } else if (!visited[getFlatIndex(nextPlayerRow, nextPlayerCol)][getFlatIndex(boxRow, boxCol)]) {
74                // Mark this as a visited state and add it to the front of the queue
75                visited[getFlatIndex(nextPlayerRow, nextPlayerCol)][getFlatIndex(boxRow, boxCol)] = true;
76                // Add new player position and same box position to the queue without incrementing distance
77                queue.unshift([getFlatIndex(nextPlayerRow, nextPlayerCol), getFlatIndex(boxRow, boxCol), distance]);
78            }
79        }
80    }
81
82    // If we never reach the target, return -1
83    return -1;
84}
85
86// Assume the 'CircularDeque' class from your code stays the same, just recalling it here
87// Since we should avoid class definitions, only the minPushBox function is provided
88// For completeness, in an actual usage scenario, the Deque class should be included
89

Time and Space Complexity

The provided Python code is designed to solve a problem where we have a grid and need to determine the minimum number of moves to push a box to the target location. The algorithm uses a breadth-first search (BFS) approach by maintaining a deque q.

Time Complexity:

The algorithm performs BFS, visiting each cell potentially multiple times depending on the movement of the player (S) and the box (B). In the worst case, the player and the box can be in every position in the grid with every possible combination, which gives us O((m * n) * (m * n)) because for every player position, the box can be in m * n positions, and the player itself can be in m * n positions.

The branching factor (the number of child nodes for a given node) at each step can be up to 4, corresponding to the four possible directions the player can move. However, since we're processing the queue's elements in a deque which is optimized for fast insertion and deletion operations, the complexity for each operation in deque is O(1). Nevertheless, the dominant factor here is the number of elements that can possibly enter the queue, making the time complexity O((m * n) * (m * n)).
Space Complexity:

For space complexity, we store a visited set vis that keeps track of whether a particular state has been visited, where a state is defined as the combination of the player's and the box's positions. This visited set will be as large as m * n * m * n in the worst case, leading to a space complexity of O((m * n) * (m * n)).

We also use additional space for the deque q which in the worst case could also have all m * n * m * n combinations, but this does not add to the space complexity asymptotically, as the visited set is already of that size.

In summary:

Time Complexity: O((m * n) * (m * n))
Space Complexity: O((m * n) * (m * n))

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know