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

CStorekeeper 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 a grid of size n*m, where each element is a wall, floor, or a box.

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

Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means 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.
Example 4:

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

# Solution

Approach 1: BFS (or A*) -- the state needs to contain the locations of both the person and the box.

# Code (Python)

Approach 1:

``````    def minPushBox(self, grid: List[List[str]]) -> int:
# the state to keep needs to have both the coord of the box, and the person, to avoid the case where the person can't reach the other side of the box
# can use A* to converge more quickly
# https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/431061/A-star-search
rows, cols = len(grid), len(grid[0])
for r in range(rows):
for c in range(cols):
if grid[r][c] == "T":
target = (r, c)
if grid[r][c] == "B":
start_box = (r, c)
if grid[r][c] == "S":
start_person = (r, c)

def heuristic(box):
return abs(target[0] - box[0]) + abs(target[1] - box[1])

def out_bounds(location):  # return whether the location is in the grid and not a wall
r, c = location
if r < 0 or r >= rows:
return True
if c < 0 or c >= cols:
return True
return grid[r][c] == "#"

heap = [[heuristic(start_box), 0, start_person, start_box]]
visited = set()

while heap:
_, moves, person, box = heapq.heappop(heap)
if box == target:
return moves
if (person, box) in visited: # do not visit same state again
continue

for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
new_person = (person[0] + dr, person[1] + dc)
if out_bounds(new_person):
continue

if new_person == box: # if made a push
new_box = (box[0] + dr, box[1] + dc)
if out_bounds(new_box):
continue
heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])
else: # if the person moved without pushing the box
heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box]) # box remains same

return -1
``````

Approach 1:

Approach 2: