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 ingridif 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 thegrid. - 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.lengthn == grid[i].length1 <= m, n <= 20gridcontains only characters'.','#','S','T', or'B'.- There is only one character
'S','B', and'T'in thegrid.
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[0].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()
set.add(key(box))
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]))) {
set.add(key([nx, ny]))
tmp.push([nx, ny])
}
}
}
q = tmp
}
return false
}
let q = [[0, box, person]]
const dkey = (a, b) => `${a[0]},${a[1]}_${b[0]},${b[1]}`
const set = new Set()
set.add(dkey(box, person))
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[0], b[1] + 1],
[b[0], b[1] - 1],
[b[0] + 1, b[1]],
[b[0] - 1, b[1]],
]
const pArr = [
[b[0], b[1] - 1],
[b[0], b[1] + 1],
[b[0] - 1, b[1]],
[b[0] + 1, b[1]],
]
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])
set.add(nk)
}
}
}
q = tmp
}
return -1
}
Input
grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output
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[0])
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:
visited.add((pX, pY, bX, bY))
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
Input
grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output
3