What is the best approach to solve Minimum Moves to Move a Box to Their Target Location?

Represent each state as (player_row, player_col, box_row, box_col) and use BFS with a priority queue to count minimal box pushes efficiently.

Do I need to count player moves without pushing?

No, only pushes count toward the move total; player walking without pushing does not increment the count.

Can the box be pulled instead of pushed?

No, the rules only allow pushing; your BFS must ensure the player is in position behind the box before pushing.

What data structures help avoid revisiting states?

Use a set or hash map keyed by both box and player positions to track visited states and prevent cycles.

How does the Array plus Breadth-First Search pattern apply here?

The grid is represented as a 2D array, and BFS systematically explores all reachable box pushes, optimizing with state tracking and priority.

#1263

Hard

auto_awesome图·搜索

LeetCode 题解工作台

推箱子

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：玩家用字符 'S' 表示，只要他在地板上，就可以在网格…

数组广度优先搜索堆（优先队列）矩阵

题目描述

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 '.' 表示，意味着可以自由行走。
墙用字符 '#' 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。

返回将箱子推到目标位置的最小推动次数，如果无法做到，请返回 -1。

示例 1：

输入：grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#",".","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：3
解释：我们只需要返回推箱子的次数。

示例 2：

输入：grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#","#","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：-1

示例 3：

输入：grid = [["#","#","#","#","#","#"],
             ["#","T",".",".","#","#"],
             ["#",".","#","B",".","#"],
             ["#",".",".",".",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：5
解释：向下、向左、向左、向上再向上。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid 仅包含字符 '.', '#', 'S' , 'T', 以及 'B'。
grid 中 'S', 'B' 和 'T' 各只能出现一个。

lightbulb

解题思路

方法一：双端队列 + BFS

我们把玩家的位置和箱子的位置看成一个状态，即 $(s_i, s_j, b_i, b_j)$ ，其中 $(s_i, s_j)$ 是玩家的位置，而 $(b_i, b_j)$ 是箱子的位置。在代码实现上，我们定义一个函数 $f(i, j)$ ，它将二维坐标 $(i, j)$ 映射到一个一维的状态编号，即 $f(i, j) = i \times n + j$ ，其中 $n$ 是网格的列数。那么玩家和箱子的状态就是 $(f(s_i, s_j), f(b_i, b_j))$ 。

我们首先遍历网格，找到玩家和箱子的初始位置，记为 $(s_i, s_j)$ 和 $(b_i, b_j)$ 。

然后，我们定义一个双端队列 $q$ ，其中每个元素都是一个三元组 $(f(s_i, s_j), f(b_i, b_j), d)$ ，表示玩家位于 $(s_i, s_j)$ ，箱子位于 $(b_i, b_j)$ ，并且已经进行了 $d$ 次推动。初始时，我们将 $(f(s_i, s_j), f(b_i, b_j), 0)$ 加入队列 $q$ 。

另外，我们用一个二维数组 $vis$ 记录每个状态是否已经访问过，初始时 $vis[f(s_i, s_j), f(b_i, b_j)]$ 标记为已访问。

接下来，我们开始进行广度优先搜索。

在每一步搜索中，我们取出队头元素 $(f(s_i, s_j), f(b_i, b_j), d)$ ，并检查是否满足 $grid[b_i][b_j] = 'T'$ ，如果是，说明箱子已经被推到目标位置，此时将 $d$ 作为答案返回即可。

否则，我们枚举玩家的下一步移动方向，玩家新的位置记为 $(s_x, s_y)$ ，如果 $(s_x, s_y)$ 是一个合法的位置，我们判断此时 $(s_x, s_y)$ 是否与箱子的位置 $(b_i, b_j)$ 相同：

如果相同，说明当前玩家到达了箱子的位置，并且推动箱子往前走了一步。箱子新的位置为 $(b_x, b_y)$ ，如果 $(b_x, b_y)$ 是一个合法的位置，且状态 $(f(s_x, s_y), f(b_x, b_y))$ 没有被访问过，那么我们就将 $(f(s_x, s_y), f(b_x, b_y), d + 1)$ 加入队列 $q$ 的末尾，并将 $vis[f(s_x, s_y), f(b_x, b_y)]$ 标记为已访问。
如果不同，说明当前玩家没有推动箱子，那么我们只需要判断状态 $(f(s_x, s_y), f(b_i, b_j))$ 是否被访问过，如果没有被访问过，那么我们就将 $(f(s_x, s_y), f(b_i, b_j), d)$ 加入队列 $q$ 的头部，并将 $vis[f(s_x, s_y), f(b_i, b_j)]$ 标记为已访问。

继续进行广度优先搜索，直到队列为空为止。

注意，如果推动箱子，那么推动次数 $d$ 需要加 $1$ ，并且新的状态加入到队列 $q$ 的末尾；如果没推动箱子，那么推动次数 $d$ 不变，新的状态加入到队列 $q$ 的头部。

最后，如果没有找到合法的推动方案，那么返回 $-1$ 。

时间复杂度 $O(m^2 \times n^2)$ ，空间复杂度 $O(m^2 \times n^2)$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数。

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

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        def f(i: int, j: int) -> int:
            return i * n + j

        def check(i: int, j: int) -> bool:
            return 0 <= i < m and 0 <= j < n and grid[i][j] != "#"

        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == "S":
                    si, sj = i, j
                elif c == "B":
                    bi, bj = i, j
        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        q = deque([(f(si, sj), f(bi, bj), 0)])
        vis = [[False] * (m * n) for _ in range(m * n)]
        vis[f(si, sj)][f(bi, bj)] = True
        while q:
            s, b, d = q.popleft()
            bi, bj = b // n, b % n
            if grid[bi][bj] == "T":
                return d
            si, sj = s // n, s % n
            for a, b in pairwise(dirs):
                sx, sy = si + a, sj + b
                if not check(sx, sy):
                    continue
                if sx == bi and sy == bj:
                    bx, by = bi + a, bj + b
                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:
                        continue
                    vis[f(sx, sy)][f(bx, by)] = True
                    q.append((f(sx, sy), f(bx, by), d + 1))
                elif not vis[f(sx, sy)][f(bi, bj)]:
                    vis[f(sx, sy)][f(bi, bj)] = True
                    q.appendleft((f(sx, sy), f(bi, bj), d))
        return -1

speed

复杂度分析

指标	值
时间	complexity depends on the number of reachable states, which is O(m _n_ m _n) in the worst case, as each combination of player and box positions can be explored. Space complexity similarly depends on storing visited states and BFS queue, requiring O(m_ n _m_ n) memory in the worst case.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect clear state representation combining player and box positions.
question_mark
Ask about BFS versus DFS trade-offs for minimizing box pushes.
question_mark
Look for handling of unreachable states and pruning redundant paths.

warning

常见陷阱

外企场景

error
Confusing player movement with box pushes; only pushes count.
error
Not tracking visited states fully with both player and box positions, leading to infinite loops.
error
Failing to validate that the player can reach the push position before attempting a box push.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Multiple boxes and targets requiring multi-object BFS.
arrow_right_alt
Adding weighted pushes where each push has a cost instead of uniform counting.
arrow_right_alt
Larger grids with teleporters or moving obstacles affecting reachability.

help

常见问题

外企场景

继续练习

#1368 使网格图至少有一条有效路径的最小代价 #1631 最小体力消耗路径 #778 水位上升的泳池中游泳