Minimum Moves to Move a Box to Their Target Location Solution
Minimum Moves to Move a Box to Their Target Location solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Moves to Move a Box to Their Target Location is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Matrix, Breadth-First Search, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Storekeeper is a game where a player pushes a box around a warehouse to a target. The warehouse is an m x n grid given as a list of strings, one per row:
'S'is the player,'B'the box and'T'the target — exactly one of each;'.'is a free floor cell and'#'a wall.
The player walks up, down, left or right onto free floor cells (never through the box or a wall). Standing next to the box and walking into it pushes the box one cell in that direction, which is allowed only if the cell beyond the box is free floor inside the grid.
Return the minimum number of pushes needed to move the box onto the target, or -1 if it cannot be done. Walking without pushing costs nothing.
Example 1
Input: grid = ["######","#T####","#..B.#","#.##.#","#...S#","######"]
Output: 3
Explanation: Push the box left twice, then walk around and push it up onto the target.
Example 2
Input: grid = ["######","#T####","#..B.#","####.#","#...S#","######"]
Output: -1
Explanation: The player can never get to the right side of the box to push it left.
Example 3
Input: grid = ["######","#T..##","#.#B.#","#....#","#...S#","######"]
Output: 5
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid contains only the characters '.', '#', 'S', 'T' and 'B'there is exactly one 'S', one 'B' and one 'T' in grid
Hints for Minimum Moves to Move a Box to Their Target Location
Hint 1
The box alone is not a full state: whether a push is possible depends on where the player is. Use
(box cell, player cell)as the state.Hint 2
A player step that does not touch the box costs 0 pushes; a step into the box moves the box and costs 1. That is a shortest path with edge weights 0 and 1.
Hint 3
Process states in layers by push count: within a layer, expand all 0-cost walks first (they stay in the layer); pushes go to the next layer. The first time the box sits on the target, the layer number is the answer.
How to solve Minimum Moves to Move a Box to Their Target Location
Search over pairs (box, player). Walking is free and pushing costs one, so this is a 0-1 shortest path: expand everything reachable without pushing before moving on to states that need one more push.
Approach
- Locate
S,BandT. Number cells0..m·n-1and encode a state asbox · (m·n) + player. - Start layer 0 with the initial state. For the current layer
d, scan its list (which grows while scanning): skip a state whose recorded distance is notd; if its box is on the target, returnd. - For each of the four directions, let the player step to the neighbouring cell. If that cell is the box and the cell beyond the box is free, the box moves there — record the new state at
d + 1in the next layer. Otherwise, if the cell is free floor, record the new state atdand append it to the current layer. - When a layer is exhausted, move to the next one. If no layer remains, return
-1.
Why it works
Every state in layer d is reachable with exactly d pushes and no fewer: zero-cost moves are explored completely before any d + 1 state is processed, which is the 0-1 BFS invariant (Dijkstra with only two edge weights). The box first reaches the target in the lowest layer that contains such a state, so the answer is minimal.
Complexity
- Time —
O((m · n)^2) - Space —
O((m · n)^2)
Pitfalls
- Searching on box positions alone, ignoring where the player can stand, accepts pushes from the wrong side.
- The player cannot walk through the box while getting into position.
- A state can first be reached by a push and later, in the same round, more cheaply by a walk — keep the smaller distance.
Reference solution
Python
from typing import List
def minPushBox(grid: List[str]) -> int:
m, n = len(grid), len(grid[0])
N = m * n
S = B = T = -1
for r in range(m):
for c in range(n):
ch = grid[r][c]
if ch == 'S':
S = r * n + c
elif ch == 'B':
B = r * n + c
elif ch == 'T':
T = r * n + c
def free(r, c):
return 0 <= r < m and 0 <= c < n and grid[r][c] != '#'
dist = [-1] * (N * N)
start = B * N + S
dist[start] = 0
cur = [start]
d = 0
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
while cur:
nxt = []
i = 0
while i < len(cur):
st = cur[i]
i += 1
if dist[st] != d:
continue
b, p = divmod(st, N)
if b == T:
return d
br, bc = divmod(b, n)
pr, pc = divmod(p, n)
for dr, dc in dirs:
nr, nc = pr + dr, pc + dc
if not free(nr, nc):
continue
np_ = nr * n + nc
if np_ == b:
if not free(br + dr, bc + dc):
continue
ns = ((br + dr) * n + bc + dc) * N + np_
if dist[ns] == -1:
dist[ns] = d + 1
nxt.append(ns)
else:
ns = b * N + np_
if dist[ns] == -1 or dist[ns] > d:
dist[ns] = d
cur.append(ns)
cur = nxt
d += 1
return -1Java
public static int minPushBox(String[] grid) {
int m = grid.length, n = grid[0].length(), N = m * n, S = -1, B = -1, T = -1;
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
char ch = grid[r].charAt(c);
if (ch == 'S') S = r * n + c; else if (ch == 'B') B = r * n + c; else if (ch == 'T') T = r * n + c;
}
int[] dist = new int[N * N];
Arrays.fill(dist, -1);
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int start = B * N + S;
dist[start] = 0;
List<Integer> cur = new ArrayList<>();
cur.add(start);
int d = 0;
while (!cur.isEmpty()) {
List<Integer> nxt = new ArrayList<>();
for (int h = 0; h < cur.size(); h++) {
int st = cur.get(h);
if (dist[st] != d) continue;
int b = st / N, p = st % N;
if (b == T) return d;
int br = b / n, bc = b % n, pr = p / n, pc = p % n;
for (int k = 0; k < 4; k++) {
int nr = pr + dr[k], nc = pc + dc[k];
if (!boxFree(grid, m, n, nr, nc)) continue;
int np = nr * n + nc;
if (np == b) {
if (!boxFree(grid, m, n, br + dr[k], bc + dc[k])) continue;
int ns = ((br + dr[k]) * n + bc + dc[k]) * N + np;
if (dist[ns] == -1) { dist[ns] = d + 1; nxt.add(ns); }
} else {
int ns = b * N + np;
if (dist[ns] == -1 || dist[ns] > d) { dist[ns] = d; cur.add(ns); }
}
}
}
cur = nxt;
d++;
}
return -1;
}
static boolean boxFree(String[] grid, int m, int n, int r, int c) {
return r >= 0 && c >= 0 && r < m && c < n && grid[r].charAt(c) != '#';
}C++
int minPushBox(vector<string>& grid) {
int m = grid.size(), n = grid[0].size(), N = m * n, S = -1, B = -1, T = -1;
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
char ch = grid[r][c];
if (ch == 'S') S = r * n + c; else if (ch == 'B') B = r * n + c; else if (ch == 'T') T = r * n + c;
}
auto freeCell = [&](int r, int c) { return r >= 0 && c >= 0 && r < m && c < n && grid[r][c] != '#'; };
vector<int> dist(N * N, -1);
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
int start = B * N + S;
dist[start] = 0;
vector<int> cur{start};
int d = 0;
while (!cur.empty()) {
vector<int> nxt;
for (size_t h = 0; h < cur.size(); h++) {
int st = cur[h];
if (dist[st] != d) continue;
int b = st / N, p = st % N;
if (b == T) return d;
int br = b / n, bc = b % n, pr = p / n, pc = p % n;
for (int k = 0; k < 4; k++) {
int nr = pr + dr[k], nc = pc + dc[k];
if (!freeCell(nr, nc)) continue;
int np = nr * n + nc;
if (np == b) {
if (!freeCell(br + dr[k], bc + dc[k])) continue;
int ns = ((br + dr[k]) * n + bc + dc[k]) * N + np;
if (dist[ns] == -1) { dist[ns] = d + 1; nxt.push_back(ns); }
} else {
int ns = b * N + np;
if (dist[ns] == -1 || dist[ns] > d) { dist[ns] = d; cur.push_back(ns); }
}
}
}
cur = nxt;
d++;
}
return -1;
}JavaScript
var minPushBox = function(grid) {
var m = grid.length, n = grid[0].length, N = m * n, S = -1, B = -1, T = -1;
for (var r = 0; r < m; r++) for (var c = 0; c < n; c++) {
var ch = grid[r][c];
if (ch === "S") S = r * n + c; else if (ch === "B") B = r * n + c; else if (ch === "T") T = r * n + c;
}
var free = function(rr, cc) { return rr >= 0 && cc >= 0 && rr < m && cc < n && grid[rr][cc] !== "#"; };
var dist = new Array(N * N);
for (var i = 0; i < N * N; i++) dist[i] = -1;
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
var start = B * N + S;
dist[start] = 0;
var cur = [start], d = 0;
while (cur.length) {
var nxt = [];
for (var h = 0; h < cur.length; h++) {
var st = cur[h];
if (dist[st] !== d) continue;
var b = Math.floor(st / N), p = st % N;
if (b === T) return d;
var br = Math.floor(b / n), bc = b % n, pr = Math.floor(p / n), pc = p % n;
for (var k = 0; k < 4; k++) {
var nr = pr + dr[k], nc = pc + dc[k];
if (!free(nr, nc)) continue;
var np = nr * n + nc, ns;
if (np === b) {
if (!free(br + dr[k], bc + dc[k])) continue;
ns = ((br + dr[k]) * n + bc + dc[k]) * N + np;
if (dist[ns] === -1) { dist[ns] = d + 1; nxt.push(ns); }
} else {
ns = b * N + np;
if (dist[ns] === -1 || dist[ns] > d) { dist[ns] = d; cur.push(ns); }
}
}
}
cur = nxt;
d++;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal