1263. Minimum Moves to Move a Box to Their Target Location LeetCode Solution
In this guide, you will get 1263. Minimum Moves to Move a Box to Their Target Location LeetCode Solution with the best time and space complexity. The solution to Minimum Moves to Move a Box to Their Target Location problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Moves to Move a Box to Their Target Location solution in C++
- Minimum Moves to Move a Box to Their Target Location solution in Java
- Minimum Moves to Move a Box to Their Target Location solution in Python
- Additional Resources
Problem Statement of Minimum Moves to Move a Box to Their Target Location
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:
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.
Complexity Analysis
- Time Complexity: O(m^2n^2)
- Space Complexity: O(m^2n^2)
1263. Minimum Moves to Move a Box to Their Target Location LeetCode Solution in C++
class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
vector<int> box;
vector<int> player;
vector<int> 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};
// (boxX, boxY, playerX, playerY)
queue<tuple<int, int, int, int>> q{
{{box[0], box[1], player[0], player[1]}}};
vector<vector<vector<vector<bool>>>> seen(
m, vector<vector<vector<bool>>>(
n, vector<vector<bool>>(m, vector<bool>(n))));
seen[box[0]][box[1]][player[0]][player[1]] = true;
for (int step = 0; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [boxX, boxY, playerX, playerY] = q.front();
q.pop();
if (boxX == target[0] && boxY == target[1])
return step;
for (int k = 0; k < 4; ++k) {
const int nextBoxX = boxX + dirs[k % 4][0];
const int nextBoxY = boxY + dirs[k % 4][1];
if (isInvalid(grid, nextBoxX, nextBoxY))
continue;
if (seen[nextBoxX][nextBoxY][boxX][boxY])
continue;
const int fromX = boxX + dirs[(k + 2) % 4][0];
const int fromY = boxY + dirs[(k + 2) % 4][1];
if (isInvalid(grid, fromX, fromY))
continue;
if (canGoTo(grid, playerX, playerY, fromX, fromY, boxX, boxY)) {
seen[nextBoxX][nextBoxY][boxX][boxY] = true;
q.emplace(nextBoxX, nextBoxY, boxX, boxY);
}
}
}
return -1;
}
private:
static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// Returns true if (playerX, playerY) can go to (fromX, fromY).
bool canGoTo(const vector<vector<char>>& grid, int playerX, int playerY,
int fromX, int fromY, int boxX, int boxY) {
queue<pair<int, int>> q{{{playerX, playerY}}};
vector<vector<bool>> seen(grid.size(), vector<bool>(grid[0].size()));
seen[playerX][playerY] = true;
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
if (i == fromX && j == fromY)
return true;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (isInvalid(grid, x, y))
continue;
if (seen[x][y])
continue;
if (x == boxX && y == boxY)
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}
return false;
}
bool isInvalid(const vector<vector<char>>& grid, int playerX, int playerY) {
return playerX < 0 || playerX == grid.size() || playerY < 0 ||
playerY == grid[0].size() || grid[playerX][playerY] == '#';
}
};
/* code provided by PROGIEZ */1263. Minimum Moves to Move a Box to Their Target Location LeetCode Solution in Java
class Solution {
public int minPushBox(char[][] grid) {
record T(int boxX, int boxY, int playerX, int playerY) {}
final int m = grid.length;
final int n = grid[0].length;
int[] box = {-1, -1};
int[] player = {-1, -1};
int[] target = {-1, -1};
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 'B')
box = new int[] {i, j};
else if (grid[i][j] == 'S')
player = new int[] {i, j};
else if (grid[i][j] == 'T')
target = new int[] {i, j};
Queue<T> q = new ArrayDeque<>(List.of(new T(box[0], box[1], player[0], player[1])));
boolean[][][][] seen = new boolean[m][n][m][n];
seen[box[0]][box[1]][player[0]][player[1]] = true;
for (int step = 0; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int boxX = q.peek().boxX;
final int boxY = q.peek().boxY;
final int playerX = q.peek().playerX;
final int playerY = q.poll().playerY;
if (boxX == target[0] && boxY == target[1])
return step;
for (int k = 0; k < 4; ++k) {
final int nextBoxX = boxX + dirs[k][0];
final int nextBoxY = boxY + dirs[k][1];
if (isInvalid(grid, nextBoxX, nextBoxY))
continue;
if (seen[nextBoxX][nextBoxY][boxX][boxY])
continue;
final int fromX = boxX + dirs[(k + 2) % 4][0];
final int fromY = boxY + dirs[(k + 2) % 4][1];
if (isInvalid(grid, fromX, fromY))
continue;
if (canGoTo(grid, playerX, playerY, fromX, fromY, boxX, boxY)) {
seen[nextBoxX][nextBoxY][boxX][boxY] = true;
q.offer(new T(nextBoxX, nextBoxY, boxX, boxY));
}
}
}
return -1;
}
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// Returns true if (playerX, playerY) can go to (fromX, fromY).
private boolean canGoTo(char[][] grid, int playerX, int playerY, int fromX, int fromY, int boxX,
int boxY) {
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(playerX, playerY)));
boolean[][] seen = new boolean[grid.length][grid[0].length];
seen[playerX][playerY] = true;
while (!q.isEmpty()) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
if (i == fromX && j == fromY)
return true;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (isInvalid(grid, x, y))
continue;
if (seen[x][y])
continue;
if (x == boxX && y == boxY)
continue;
q.offer(new Pair<>(x, y));
seen[x][y] = true;
}
}
return false;
}
private boolean isInvalid(char[][] grid, int playerX, int playerY) {
return playerX < 0 || playerX == grid.length || playerY < 0 || playerY == grid[0].length ||
grid[playerX][playerY] == '#';
}
}
// code provided by PROGIEZ1263. Minimum Moves to Move a Box to Their Target Location LeetCode Solution in Python
class Solution:
def minPushBox(self, grid: list[list[str]]) -> int:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(grid)
n = len(grid[0])
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 isInvalid(playerX: int, playerY: int) -> bool:
return (playerX < 0 or playerX == m or playerY < 0 or playerY == n or
grid[playerX][playerY] == '#')
def canGoTo(
playerX: int,
playerY: int,
fromX: int,
fromY: int,
boxX: int,
boxY: int
) -> bool:
"""Returns True if (playerX, playerY) can go to (fromX, fromY)."""
q = collections.deque([(playerX, playerY)])
seen = {(playerX, playerY)}
while q:
i, j = q.popleft()
if i == fromX and j == fromY:
return True
for dx, dy in dirs:
x = i + dx
y = j + dy
if isInvalid(x, y):
continue
if (x, y) in seen:
continue
if x == boxX and y == boxY:
continue
q.append((x, y))
seen.add((x, y))
return False
# (boxX, boxY, playerX, playerY)
q = collections.deque([(box[0], box[1], player[0], player[1])])
seen = {(box[0], box[1], player[0], player[1])}
step = 0
while q:
for _ in range(len(q)):
boxX, boxY, playerX, playerY = q.popleft()
if boxX == target[0] and boxY == target[1]:
return step
for k, (dx, dy) in enumerate(dirs):
nextBoxX = boxX + dx
nextBoxY = boxY + dy
if isInvalid(nextBoxX, nextBoxY):
continue
if (nextBoxX, nextBoxY, boxX, boxY) in seen:
continue
fromX = boxX + dirs[(k + 2) % 4][0]
fromY = boxY + dirs[(k + 2) % 4][1]
if isInvalid(fromX, fromY):
continue
if canGoTo(playerX, playerY, fromX, fromY, boxX, boxY):
q.append((nextBoxX, nextBoxY, boxX, boxY))
seen.add((nextBoxX, nextBoxY, boxX, boxY))
step += 1
return -1
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.