# Minimum Moves to Move a Box to Their Target Location
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-move-a-box-to-their-target-location
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Heap (Priority Queue), Matrix
---
## Problem
A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by an `m x n` grid of characters `grid` where each element is a wall, floor, or box.

Your task is to move the box `'B'` to the target position `'T'` under the following rules:

* The character `'S'` represents the player. The player can move up, down, left, right in `grid` if it is a floor (empty cell).
* The character `'.'` represents the floor which means a free cell to walk.
* The character `'#'` represents the wall which means an obstacle (impossible to walk there).
* There is only one box `'B'` and one target cell `'T'` in the `grid`.
* The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a **push**.
* The player cannot walk through the box.

Return _the minimum number of **pushes** to move the box to the target_. If there is no way to reach the target, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-moves-to-move-a-box-to-their-target-location/image0.png) 

**Input:** grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
**Output:** 3
**Explanation:** We return only the number of times the box is pushed.

**Example 2:**

**Input:** grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
**Output:** -1

**Example 3:**

**Input:** grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
**Output:** 5
**Explanation:** push the box down, left, left, up and up.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 20`
* `grid` contains only characters `'.'`, `'#'`, `'S'`, `'T'`, or `'B'`.
* There is only one character `'S'`, `'B'`, and `'T'` in the `grid`.

# Approaches
## Brute-Force Depth First Search (DFS)
This approach attempts to solve the problem by exploring every possible sequence of moves using recursion. It's a brute-force method that tries all paths from the start state until the target is reached. A global variable keeps track of the minimum number of pushes found so far, which helps in pruning branches of the search that are already worse than the best solution found.
**Time:** Potentially exponential, O(4^S) where S is the number of states (S = (m*n)^2). Without memoization, the same states are visited repeatedly through different paths, leading to an explosion in computation. · **Space:** O((m*n)^2) in the worst case. The space is dominated by the recursion stack depth, which can be as large as the total number of unique states, S = m * n * m * n.
**Pros:** Conceptually simple to understand if one is familiar with recursion and backtracking.
**Cons:** Extremely inefficient due to the re-computation of states. The same subproblem (finding the minimum pushes from a given state) is solved multiple times.; The number of possible paths can be enormous, leading to a very deep recursion and a large state space to explore.; Almost certain to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for non-trivial grids.
### Explanation
The core of this method is a recursive Depth First Search (DFS) function that explores the state space. A state is defined by the tuple `(box_row, box_col, player_row, player_col)`. The function systematically tries every possible move from the current state.

There are two types of moves:
1.  **Player Move:** The player moves to an adjacent empty cell. This does not increase the push count.
2.  **Box Push:** The player, standing next to the box, pushes it to an adjacent empty cell. This increases the push count by one.

The recursion continues until the box reaches the target. To prevent infinite loops (e.g., moving the player back and forth), we must keep track of the states visited in the current path. This approach is exhaustive and, without memoization (which would transform it into a dynamic programming solution), it is highly inefficient as it explores many redundant paths.
### Algorithm
*   Initialize a global variable `min_pushes` to infinity.
*   Define a recursive function, for example, `dfs(box_r, box_c, player_r, player_c, current_pushes)`.
*   To avoid infinite loops, use a `visited` set to track states `(box_pos, player_pos)` within the current recursion path. Add the current state to the set before making recursive calls and remove it after they return.
*   **Pruning Step:** If `current_pushes` is already greater than or equal to `min_pushes`, there is no need to explore further down this path, so return immediately.
*   **Base Case:** If the box's position `(box_r, box_c)` matches the target location, it means a valid path has been found. Update `min_pushes = min(min_pushes, current_pushes)` and return.
*   **Recursive Step:**
    1.  **Explore Player Moves:** For each of the four directions, if the player can move to a new cell `(npr, npc)` (i.e., it's a floor and not the box's location) and the new state `(box_r, box_c, npr, npc)` has not been visited in the current path, make a recursive call: `dfs(box_r, box_c, npr, npc, current_pushes)`.
    2.  **Explore Box Pushes:** If the player is adjacent to the box, they can attempt to push it. For each valid push that moves the box to `(new_br, new_bc)` and the player to the box's old spot `(box_r, box_c)`, and the new state has not been visited, make a recursive call: `dfs(new_br, new_bc, box_r, box_c, current_pushes + 1)`.
*   The initial call to the function would be with the starting positions of the box and player, and `current_pushes` as 0.
*   After the initial call returns, if `min_pushes` is still infinity, it means the target is unreachable; otherwise, it holds the minimum number of pushes.

## Optimal: Shortest Path on State Space using 0-1 BFS
This optimal approach models the problem as finding the shortest path in a state graph. A state is uniquely identified by the combination of the box's position and the player's position. Since we want to minimize the number of pushes (cost 1) while player moves are free (cost 0), this is a classic shortest path problem on a graph with 0-1 edge weights. This type of problem is perfectly suited for a 0-1 Breadth-First Search (BFS) using a deque, which is generally more efficient than using a priority queue as in Dijkstra's algorithm for this specific case.
**Time:** O((m*n)^2). The number of states is S = m * n * m * n. Each state is enqueued and dequeued at most once. From each state, we explore a constant number of subsequent states (4 for player moves, 4 for box pushes). Therefore, the total time complexity is proportional to the number of states. · **Space:** O((m*n)^2). The space is dominated by the 4D `dist` array, which stores the minimum pushes for every possible state. The deque also stores states, but its size is bounded by the total number of states.
**Pros:** Guaranteed to find the optimal solution (minimum number of pushes).; It is very efficient for the given constraints of the problem.; The 0-1 BFS structure is a clever and performant way to handle the two different costs of moves.
**Cons:** The main drawback is the high space complexity, O((m*n)^2), required for the distance/visited array. For the given constraints (m, n <= 20), this is acceptable, but it could be an issue for larger grids.
### Explanation
The state of the system can be fully described by `(box_row, box_col, player_row, player_col)`. We can think of each unique state as a node in a giant graph. Our goal is to find the shortest path from the initial state to any state where the box is on the target location.

The transitions between states (edges in the graph) have costs:
*   **Player Move:** When the player moves without pushing the box, the state changes, but the number of pushes does not. This is a **0-cost** edge.
*   **Box Push:** When the player pushes the box, the state changes, and the number of pushes increases by one. This is a **1-cost** edge.

A 0-1 BFS is an ideal algorithm for this scenario. It uses a deque (double-ended queue). When exploring a state, new states reached via 0-cost edges (player moves) are added to the front of the deque, while states reached via 1-cost edges (box pushes) are added to the back. This ensures that we always explore all possible free player movements for a given number of pushes before considering the next push. This correctly finds the path with the minimum number of pushes.

We use a 4D array to store the minimum pushes to reach any state, which also helps us avoid visiting the same state with a higher or equal push count.

```java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] sPos = null, bPos = null, tPos = null;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S') {
                    sPos = new int[]{i, j};
                    grid[i][j] = '.'; // Treat player's start as floor
                } else if (grid[i][j] == 'B') {
                    bPos = new int[]{i, j};
                    grid[i][j] = '.'; // Treat box's start as floor
                } else if (grid[i][j] == 'T') {
                    tPos = new int[]{i, j};
                    grid[i][j] = '.'; // Treat target as floor
                }
            }
        }

        int[][][][] dist = new int[m][n][m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    Arrays.fill(dist[i][j][k], Integer.MAX_VALUE);
                }
            }
        }

        Deque<int[]> deque = new ArrayDeque<>();
        
        dist[bPos[0]][bPos[1]][sPos[0]][sPos[1]] = 0;
        deque.addFirst(new int[]{bPos[0], bPos[1], sPos[0], sPos[1]});

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!deque.isEmpty()) {
            int[] current = deque.pollFirst();
            int br = current[0], bc = current[1];
            int pr = current[2], pc = current[3];
            int d = dist[br][bc][pr][pc];

            if (br == tPos[0] && bc == tPos[1]) {
                return d;
            }

            // Player moves (cost 0)
            for (int i = 0; i < 4; i++) {
                int npr = pr + dr[i];
                int npc = pc + dc[i];

                if (npr >= 0 && npr < m && npc >= 0 && npc < n && grid[npr][npc] != '#' && !(npr == br && npc == bc)) {
                    if (dist[br][bc][npr][npc] > d) {
                        dist[br][bc][npr][npc] = d;
                        deque.addFirst(new int[]{br, bc, npr, npc});
                    }
                }
            }

            // Box pushes (cost 1)
            if (Math.abs(pr - br) + Math.abs(pc - bc) == 1) { // Player is adjacent to the box
                int nbr = br + (br - pr);
                int nbc = bc + (bc - pc);

                if (nbr >= 0 && nbr < m && nbc >= 0 && nbc < n && grid[nbr][nbc] != '#') {
                    if (dist[nbr][nbc][br][bc] > d + 1) {
                        dist[nbr][nbc][br][bc] = d + 1;
                        deque.addLast(new int[]{nbr, nbc, br, bc});
                    }
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
*   First, parse the grid to find the initial positions of the player 'S', the box 'B', and the target 'T'.
*   Define a state as a tuple `(box_row, box_col, player_row, player_col)`.
*   Initialize a 4D array, `dist[m][n][m][n]`, with a large value (infinity) to store the minimum pushes to reach each state. This array also implicitly acts as a `visited` array.
*   Initialize a deque (double-ended queue) for the 0-1 BFS.
*   Add the initial state `(start_br, start_bc, start_pr, start_pc)` to the front of the deque and set its distance in the `dist` array to 0.
*   While the deque is not empty:
    *   Pop a state `(br, bc, pr, pc)` from the **front** of the deque. Let its distance be `d`.
    *   If `(br, bc)` is the target position, return `d`.
    *   **Explore Player Moves (0-cost transitions):** For each of the 4 neighbors `(npr, npc)` of the player at `(pr, pc)`:
        *   If the move is valid (within bounds, not a wall, and not the box's current location) and `d < dist[br][bc][npr][npc]`:
        *   Update `dist[br][bc][npr][npc] = d`.
        *   Add the new state `(br, bc, npr, npc)` to the **front** of the deque.
    *   **Explore Box Pushes (1-cost transitions):** If the player at `(pr, pc)` is adjacent to the box at `(br, bc)`:
        *   Calculate the new box position `(nbr, nbc)` by pushing it away from the player.
        *   If the push is valid (the new box position is within bounds and not a wall) and `d + 1 < dist[nbr][nbc][br][bc]`:
        *   Update `dist[nbr][nbc][br][bc] = d + 1`.
        *   The new player position is the box's old spot `(br, bc)`. Add the new state `(nbr, nbc, br, bc)` to the **back** of the deque.
*   If the deque becomes empty and the target has not been reached, it's impossible to solve. Return -1.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  char[][] grid;
public
  int minPushBox(char[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int si = 0, sj = 0, bi = 0, bj = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 'S') {
          si = i;
          sj = j;
        } else if (grid[i][j] == 'B') {
          bi = i;
          bj = j;
        }
      }
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    Deque<int[]> q = new ArrayDeque<>();
    boolean[][] vis = new boolean[m * n][m * n];
    q.offer(new int[]{f(si, sj), f(bi, bj), 0});
    vis[f(si, sj)][f(bi, bj)] = true;
    while (!q.isEmpty()) {
      var p = q.poll();
      int d = p[2];
      bi = p[1] / n;
      bj = p[1] % n;
      if (grid[bi][bj] == 'T') {
        return d;
      }
      si = p[0] / n;
      sj = p[0] % n;
      for (int k = 0; k < 4; ++k) {
        int sx = si + dirs[k], sy = sj + dirs[k + 1];
        if (!check(sx, sy)) {
          continue;
        }
        if (sx == bi && sy == bj) {
          int bx = bi + dirs[k], by = bj + dirs[k + 1];
          if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
            continue;
          }
          vis[f(sx, sy)][f(bx, by)] = true;
          q.offer(new int[]{f(sx, sy), f(bx, by), d + 1});
        } else if (!vis[f(sx, sy)][f(bi, bj)]) {
          vis[f(sx, sy)][f(bi, bj)] = true;
          q.offerFirst(new int[]{f(sx, sy), f(bi, bj), d});
        }
      }
    }
    return -1;
  }
private
  int f(int i, int j) { return i * n + j; }
private
  boolean check(int i, int j) {
    return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minPushBox(vector<vector<char>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int si, sj, bi, bj;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 'S') {
          si = i, sj = j;
        } else if (grid[i][j] == 'B') {
          bi = i, bj = j;
        }
      }
    }
    auto f = [&](int i, int j) { return i * n + j; };
    auto check = [&](int i, int j) {
      return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
    };
    int dirs[5] = {-1, 0, 1, 0, -1};
    deque<tuple<int, int, int>> q;
    q.emplace_back(f(si, sj), f(bi, bj), 0);
    bool vis[m * n][m * n];
    memset(vis, false, sizeof(vis));
    vis[f(si, sj)][f(bi, bj)] = true;
    while (!q.empty()) {
      auto [s, b, d] = q.front();
      q.pop_front();
      si = s / n, sj = s % n;
      bi = b / n, bj = b % n;
      if (grid[bi][bj] == 'T') {
        return d;
      }
      for (int k = 0; k < 4; ++k) {
        int sx = si + dirs[k], sy = sj + dirs[k + 1];
        if (!check(sx, sy)) {
          continue;
        }
        if (sx == bi && sy == bj) {
          int bx = bi + dirs[k], by = bj + dirs[k + 1];
          if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
            continue;
          }
          vis[f(sx, sy)][f(bx, by)] = true;
          q.emplace_back(f(sx, sy), f(bx, by), d + 1);
        } else if (!vis[f(sx, sy)][f(bi, bj)]) {
          vis[f(sx, sy)][f(bi, bj)] = true;
          q.emplace_front(f(sx, sy), f(bi, bj), d);
        }
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int: def f(i: int, j: int) -> int: return i * n + j def check(i: int, j: int) -> bool: return 0 <= i < m and 0 <= j < n and grid[i][j] != "#" for i, row in enumerate(grid): for j, c in enumerate(row): if c == "S": si, sj = i, j elif c == "B": bi, bj = i, j m, n = len(grid), len(grid[0]) dirs = (- 1, 0, 1, 0, - 1) q = deque([(f(si, sj), f(bi, bj), 0)]) vis = [[False] * (m * n) for _ in range(m * n)] vis[f(si, sj)][f(bi, bj)] = True while q: s, b, d = q . popleft() bi, bj = b // n, b % n if grid[bi][bj] == "T": return d si, sj = s // n, s % n for a, b in pairwise(dirs): sx, sy = si + a, sj + b if not check(sx, sy): continue if sx == bi and sy == bj: bx, by = bi + a, bj + b if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]: continue vis[f(sx, sy)][f(bx, by)] = True q . append((f(sx, sy), f(bx, by), d + 1)) elif not vis[f(sx, sy)][f(bi, bj)]: vis[f(sx, sy)][f(bi, bj)] = True q . appendleft((f(sx, sy), f(bi, bj), d)) return - 1

```