Minimum Moves To Move A Box To Their Target Location - Leetcode Solution

Problem Statement:

Given a maze represented by a binary grid of size m x n and a box placed at cell boxStart = [iStart, jStart]. The maze is represented by a binary 2D array grid of size m x n. 1 means a wall and 0 means an empty space. You can move the box up, down, left or right. You cannot move the box into a wall or outside the maze.

You have to move the box to the target location target = [iTarget, jTarget]. You have to move the box to the target location with minimum number of moves. The box cannot be moved without the robot.

Return the minimum number of moves required to move the box to the target. If it is impossible to move the box to the target location, return -1.

Solution:

The problem can be solved using Breadth First Search (BFS). In order to use BFS, we need to represent the states and transitions in a searchable format.

State: A state is defined as the position of the robot, the position of the box and the direction that the robot is facing. We can represent the state as (x,y, bx, by) where (x,y) is the position of the robot, and (bx,by) is the position of the box.

Transition: A transition is defined as a move that the robot can make to a new state. We can represent a transition as a tuple (dx,dy) where (dx,dy) is the movement that the robot makes in the x and y directions.

Algorithm:

1. Create a queue and a set to store the states that we have already visited.
2. Enqueue the initial state into the queue.
3. While the queue is not empty, do the following: a. Dequeue the first state from the queue. b. If the current state is the target state, return the number of moves to reach this state. c. Enumerate all possible moves from the current state: 1. Check if the move is valid. A move is considered valid if the robot can move to the new position without hitting a wall, and if it can move the box to a new position without moving it into a wall or outside the grid. 2. If the move is valid and the new state has not been visited before, add the new state to the queue and mark it as visited.
4. If we have exhausted all possible states and we have not found a solution, return -1.

Code:

Here's the Python code for the solution:

from collections import deque class Solution: def minPushBox(self, grid: List[List[str]]) -> int: n = len(grid) m = len(grid[0]) delta = [(0,1),(0,-1),(1,0),(-1,0)]

    # initialize variables
    bx, by, px, py = -1, -1, -1, -1
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'B':
                bx, by = i, j
            elif grid[i][j] == 'S':
                px, py = i, j
    
    # BFS
    q = deque()
    visited = set()
    q.append((bx, by, px, py, 0))
    visited.add((bx, by, px, py))
    while q:
        bx, by, px, py, moves = q.popleft()
        if (bx, by) == (tx, ty):
            return moves
        for dx, dy in delta:
            new_px, new_py = px + dx, py + dy
            if new_px < 0 or new_px >= n or new_py < 0 or new_py >= m or grid[new_px][new_py] == '#':
                continue
            if bx == new_px and by == new_py:
                new_bx, new_by = bx + dx, by + dy
                if new_bx < 0 or new_bx >= n or new_by < 0 or new_by >= m or grid[new_bx][new_by] == '#' or (new_bx, new_by, bx, by) in visited:
                    continue
                q.append((new_bx, new_by, bx, by, moves + 1))
                visited.add((new_bx, new_by, bx, by))
            else:
                if (new_px, new_py, bx, by) in visited:
                    continue
                q.append((bx, by, new_px, new_py, moves))
                visited.add((new_px, new_py, bx, by))
    return -1

Time Complexity:

The time complexity of the solution is O(n^2 * m^2) where n and m are the dimensions of the grid. The worst case scenario is when the robot has to explore the entire grid before finding the target state.

Space Complexity:

The space complexity of the solution is also O(n^2 * m^2) because we need to store all possible states in the visited set. However, the actual space used in practice is much less because not all states can be explored due to the constraints of the problem.

1