## Algorithm

Problem Name: 1263. 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`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minPushBox = function (grid) {
let box, person, target
const m = grid.length,
n = grid.length
const dirs = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
]
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const e = grid[i][j]
if (e === 'B') box = [i, j]
else if (e === 'T') target = [i, j]
else if (e === 'S') person = [i, j]
}
}

const valid = ([i, j]) => {
return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] !== '#'
}
const key = ([i, j]) => `\${i},\${j}`

const chk = (person, newPerson, box) => {
const set = new Set()
let q = [person]
while (q.length) {
const tmp = []
const size = q.length
for (let i = 0; i < size; i++) {
const [x, y] = q[i]
if (key([x, y]) === key(newPerson)) return true
for (const [dx, dy] of dirs) {
const [nx, ny] = [x + dx, y + dy]
if (valid([nx, ny]) && !set.has(key([nx, ny]))) {
tmp.push([nx, ny])
}
}
}
q = tmp
}
return false
}

let q = [[0, box, person]]
const dkey = (a, b) => `\${a},\${a}_\${b},\${b}`
const set = new Set()
while (q.length) {
const size = q.length
const tmp = []
for (let i = 0; i < size; i++) {
const [v, b, p] = q[i]
if (key(b) === key(target)) return v
const bArr = [
[b, b + 1],
[b, b - 1],
[b + 1, b],
[b - 1, b],
]
const pArr = [
[b, b - 1],
[b, b + 1],
[b - 1, b],
[b + 1, b],
]

for (let j = 0; j < 4; j++) {
const nb = bArr[j],
np = pArr[j]
const nk = dkey(nb, b)

if (set.has(nk)) continue
if (valid(nb) && valid(np) && chk(p, np, b)) {
tmp.push([v + 1, nb, b])
}
}
}
q = tmp
}

return -1
}
``````
Copy The Code &

Input

cmd
grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]]

Output

cmd
3

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid)
for r in range(m):
for c in range(n):
if grid[r][c] == "T":
tX, tY = r, c
if grid[r][c] == "B":
bX, bY = r, c
if grid[r][c] == "S":
pX, pY = r, c

def heuristic(bX, bY):
return abs(tX - bX) + abs(tY - bY)

heap = [[heuristic(bX, bY), 0, pX, pY, bX, bY]]
visited = set()
while heap:
_, moves, pX, pY, bX, bY = heapq.heappop(heap)
if bX == tX and bY == tY:
return moves
if (pX, pY, bX, bY) not in visited:
for dx, dy in (0, 1), (1, 0), (-1, 0), (0, -1):
pX += dx
pY += dy
if 0 <= pX < m and 0 <= pY < n and grid[pX][pY] != "#":
if pX == bX and pY == bY:
bX += dx
bY += dy
if 0 <= bX < m and 0 <= bY < n and grid[bX][bY] != "#":
heapq.heappush(
heap,
[
heuristic(bX, bY) + moves + 1,
moves + 1,
pX,
pY,
bX,
bY,
],
)
bX -= dx
bY -= dy
else:
heapq.heappush(
heap, [heuristic(bX, bY) + moves, moves, pX, pY, bX, bY]
)
pX -= dx
pY -= dy
return -1
``````
Copy The Code &

Input

cmd
grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]]

Output

cmd
3