1263 Minimum Moves to Move a Box to Their Target Location

🔀 Pick One

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.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        target = init_box = init_person = (0, 0)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'T':
                    target = (i, j)
                if grid[i][j] == 'B':
                    init_box = (i, j)
                if grid[i][j] == 'S':
                    init_person = (i, j)
        
        def valid(pos: Tuple[int, int]):
            x, y = pos
            return (
                0 <= x < m and
                0 <= y < n and
                grid[x][y] != '#'
            )
        
        def can_reach(curr, dest, box):
            # dfs
            q = deque([curr])
            visited = set([curr])
            while q:
                pos = q.popleft()
                if pos == dest:
                    return True
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    next_pos = pos[0] + dx, pos[1] + dy
                    if (valid(next_pos) and
                        next_pos not in visited and
                        next_pos != box
                    ):
                        visited.add(next_pos)
                        q.append(next_pos)
            return False
        
        q = deque()
        q.append((0, init_box, init_person))
        seen = set()  # records of (box_pos, per_pos) after push

        while q:
            dist, box, person = q.popleft()
            if box == target:
                return dist
            bx, by = box
            moves = [
                # 4 cases for
                # (box pos after push + person position before push)
                ((bx+1, by), (bx-1, by)),
                ((bx-1, by), (bx+1, by)),
                ((bx, by+1), (bx, by-1)),
                ((bx, by-1), (bx, by+1)),
            ]
            for box_new, per_before in moves:
                # per_before -> box -> box_new
                # per_before is the person position beofre push
                # box is the new person position after push
                if (valid(box_new) and
                    (box_new, box) not in seen and
                    valid(per_before) and
                    can_reach(person, per_before, box)
                ):
                    seen.add((box_new, box))
                    q.append((dist + 1, box_new, box))
        return -1