LeetCode 1263. 推箱子
目录
题目描述
题意分析
网格里有一个人
S、一个箱子B、一个目标T和若干墙#。人可以在空地上任意走动，走多少步都不算代价；只有当人站在箱子正后方、把箱子朝正前方推一格时，代价才加一。问把箱子推到T最少需要几次推动，做不到返回 -1。代价函数是本题第一个必须读清楚的点：被计数的是「推」，不是「走」。人绕半张地图去换个方向推箱子，代价仍然是 1。这意味着答案的搜索层次必须以推动为单位来划分，人的走路只是一次推动能否成立的前置条件，不能混进同一个代价体系里。
第二个点是状态的刻画。很容易以为「箱子在哪」就够了，但这是错的：箱子停在同一格，人站在它的左边还是右边，下一步能推的方向完全不同——推箱子的前提是人必须先到达箱子背后那一格，而箱子本身会挡住人的通路。所以描述局面至少需要两条信息：箱子的位置，以及人的位置。约束里 $m, n \le 20$，格子数最多 400，两两组合也才 16 万个状态，这个规模明确在暗示可以放心地把「箱子位置 × 人位置」整体当作状态空间来搜。
第三个点是一次推动的合法性条件。设箱子在
(r, c)，想把它往方向d推一格，那么箱子的落点(r, c) + d必须在界内且不是墙，人的站位(r, c) - d也必须在界内且不是墙，并且人必须能从当前位置走到那个站位，途中不许穿墙、也不许穿过箱子。边界与陷阱：初始时箱子可能已经在目标上，答案是 0；箱子可能被墙彻底围死，或者人和箱子被墙隔在两个连通块里，这两种都要返回 -1；
T和S、B所在格子本身都算空地，判断可通行时只需要排除#。
解法：按推箱子次数分层 BFS
核心思路
先看暴力：把「人走一步」和「人推一格」都当成一次转移做 BFS，状态还是
(箱子位置, 人位置)。这能求出最少的总动作数，但题目要的是最少推动数，走路那些转移的边权是 0 而推动的边权是 1，这是一张 0-1 权图，直接用普通 BFS 的层数当答案是错的。瓶颈就在这里：边权不齐。修的办法有两条，一条是 0-1 BFS（用双端队列，走路从队头进、推动从队尾进），另一条更直白——把所有 0 权的边压缩掉。
观察到人走路本身不产生任何代价，那么「人从当前位置能否走到某个站位」就不必一步步搜进主状态空间，它可以被折叠成一个布尔判定：给定当前箱子位置（当作一堵临时的墙），人的起点和终点是否连通。于是主搜索的每一条边都恰好等于一次推动，边权全部为 1，普通 BFS 的层数就直接是推动次数。
由此确定状态定义：
(boxPos, playerPos)表示箱子当前在boxPos，且刚刚完成的那次推动结束后人站在playerPos。初始状态是(B, S)。从状态(boxPos, playerPos)出发，对四个方向d各尝试一次推动，若落点与站位都可通行、且人能在把boxPos视为障碍的前提下从playerPos走到站位，则产生新状态(boxPos + d, boxPos)——注意新状态里人的位置是箱子原来的格子，因为推完之后人正好顶在那儿。循环不变量是：BFS 第
k层里的每一个状态，都恰好可以用k次推动从初始局面到达，且没有更少的推法。这由 BFS 的层序性质加「每条边权重恒为 1」共同保证。因此第一次从队列里取出箱子位于目标的状态时，当前层号就是答案。去重用
visited[boxPos][playerPos]，两维都是把(row, col)压成row * cols + col的一维下标，规模 $400 \times 400$，开成二维布尔数组即可。
解题步骤
- 扫描网格定位三个关键点：一次遍历找出
B、S、T的坐标，并统一编码成row * cols + col的一维下标。用一维下标是为了让visited能开成朴素的二维数组，也让状态比较退化成两个整数比较，比存int[4]再手写哈希干净得多。- 初始化队列与访问标记：把
(box, player)入队并标记visited[box][player] = true，推动计数pushes = 0。- 按层展开：每轮先取出当前队列长度
size，只处理这size个状态，处理完再pushes++。必须先记住size再循环，否则本轮新入队的状态会被当作同一层处理，层号和推动次数就对不上了。- 出队即判终点：取出状态后先看
boxPos == target，命中就返回pushes。在出队时判、而不是在入队时判，是为了让「初始箱子已在目标」这种情况自然返回 0，不需要额外特判。- 枚举四个推动方向：对方向
d，算出箱子落点(boxRow + d0, boxCol + d1)和人的站位(boxRow - d0, boxCol - d1)。落点和站位在箱子的两侧，符号一正一负，写反了就变成「人从前面拉箱子」。两者都要过isOpen检查（界内且非#）。- 先查去重再查可达：新状态是
(nextBox, boxPos)，若visited[nextBox][boxPos]已为真直接跳过。这个顺序很重要——可达性判定是一次 $O(mn)$ 的 BFS，是整段代码里最贵的操作，把 $O(1)$ 的去重放在它前面能省掉大量重复计算。- 判定人能否绕到站位：调用
canReach(grid, playerPos, stand, boxPos)，在网格上做一次普通 BFS，把boxPos这一格额外当作障碍。不把箱子当障碍就等于允许人穿箱而过，会推出根本走不通的路线。- 入队新状态：标记
visited[nextBox][boxPos] = true后入队。标记要在入队时立刻做，而不是等出队时再做，否则同一状态可能被同层的多个前驱重复塞进队列。- 队列耗尽返回 -1：所有可达状态都展开完了还没碰到目标，说明箱子推不过去。
以下面这张图走一遍（行列都从 0 开始编号）：
#、#、#、#、#、#/#、T、#、#、#、#/#、.、.、B、.、#/#、.、#、#、.、#/#、.、.、.、S、#/#、#、#、#、#、#也就是
T在(1,1)，B在(2,3)，S在(4,4)，其余非#处为空地。初始状态(box=(2,3), player=(4,4))，pushes = 0。第 0 层：出队
((2,3), (4,4))，箱子不在目标。枚举方向：向左推，落点(2,2)是空地，站位(2,4)是空地，人从(4,4)走(3,4) → (2,4)可达，产生新状态((2,2), (2,3))；向右推落点(2,4)可通行但站位(2,2)虽可通行、人却要先经过(2,3)的箱子或绕行(3,2)（是墙），走不通，作废；向上推站位(3,3)是墙，作废；向下推落点(3,3)是墙，作废。本层结束，pushes变为 1。第 1 层：出队
((2,2), (2,3))，不在目标。向左推：落点(2,1)空地，站位(2,3)正是人当前所在，可达，得到((2,1), (2,2))。其余方向被墙挡住。pushes变为 2。第 2 层：出队
((2,1), (2,2))，不在目标。向上推：落点(1,1)就是T，站位(3,1)是空地；人从(2,2)出发，(2,1)被箱子占住不能走，于是绕(2,3) → (2,4) → (3,4) → (4,4) → (4,3) → (4,2) → (4,1) → (3,1)，可达。得到((1,1), (2,1))。pushes变为 3。第 3 层：出队
((1,1), (2,1))，boxPos == target，返回 3。这个走查同时说明了两件事：第 2 层那次推动，人绕了整整 8 步路，但代价只算 1；以及如果
canReach忘了把箱子当障碍，人会直接从(2,2)穿过(2,1)一步到(3,1)，虽然本例答案碰巧不变，但在箱子恰好卡住唯一通道的图上就会算出偏小的答案。
代码实现
class Solution {
private static final int[][] DIRECTIONS = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
private int rows;
private int cols;
public int minPushBox(char[][] grid) {
rows = grid.length;
cols = grid[0].length;
int total = rows * cols;
int box = -1;
int player = -1;
int target = -1;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
int pos = row * cols + col;
if (grid[row][col] == 'B') {
box = pos;
} else if (grid[row][col] == 'S') {
player = pos;
} else if (grid[row][col] == 'T') {
target = pos;
}
}
}
boolean[][] visited = new boolean[total][total];
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {box, player});
visited[box][player] = true;
int pushes = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] state = queue.poll();
int boxPos = state[0];
int playerPos = state[1];
if (boxPos == target) {
return pushes;
}
int boxRow = boxPos / cols;
int boxCol = boxPos % cols;
for (int[] direction : DIRECTIONS) {
int nextBoxRow = boxRow + direction[0];
int nextBoxCol = boxCol + direction[1];
int standRow = boxRow - direction[0];
int standCol = boxCol - direction[1];
if (!isOpen(grid, nextBoxRow, nextBoxCol) || !isOpen(grid, standRow, standCol)) {
continue;
}
int nextBox = nextBoxRow * cols + nextBoxCol;
int stand = standRow * cols + standCol;
if (visited[nextBox][boxPos]) {
continue;
}
// 人必须能绕到箱子背后，才能完成这一次推动。
if (!canReach(grid, playerPos, stand, boxPos)) {
continue;
}
visited[nextBox][boxPos] = true;
queue.offer(new int[] {nextBox, boxPos});
}
}
pushes++;
}
return -1;
}
private boolean canReach(char[][] grid, int start, int target, int box) {
boolean[] visited = new boolean[rows * cols];
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int pos = queue.poll();
if (pos == target) {
return true;
}
int row = pos / cols;
int col = pos % cols;
for (int[] direction : DIRECTIONS) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (!isOpen(grid, nextRow, nextCol)) {
continue;
}
int next = nextRow * cols + nextCol;
if (next == box || visited[next]) {
continue;
}
visited[next] = true;
queue.offer(next);
}
}
return false;
}
private boolean isOpen(char[][] grid, int row, int col) {
return row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#';
}
}
var pushBoxDirections = [][2]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
func minPushBox(grid [][]byte) int {
rows := len(grid)
cols := len(grid[0])
total := rows * cols
box := -1
player := -1
target := -1
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
pos := row*cols + col
if grid[row][col] == 'B' {
box = pos
} else if grid[row][col] == 'S' {
player = pos
} else if grid[row][col] == 'T' {
target = pos
}
}
}
visited := make([][]bool, total)
for i := 0; i < total; i++ {
visited[i] = make([]bool, total)
}
queue := [][2]int{{box, player}}
visited[box][player] = true
pushes := 0
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
state := queue[i]
boxPos := state[0]
playerPos := state[1]
if boxPos == target {
return pushes
}
boxRow := boxPos / cols
boxCol := boxPos % cols
for _, direction := range pushBoxDirections {
nextBoxRow := boxRow + direction[0]
nextBoxCol := boxCol + direction[1]
standRow := boxRow - direction[0]
standCol := boxCol - direction[1]
if !isPushBoxOpen(grid, nextBoxRow, nextBoxCol) || !isPushBoxOpen(grid, standRow, standCol) {
continue
}
nextBox := nextBoxRow*cols + nextBoxCol
stand := standRow*cols + standCol
if visited[nextBox][boxPos] {
continue
}
// 人必须能绕到箱子背后，才能完成这一次推动。
if !canPushBoxReach(grid, playerPos, stand, boxPos) {
continue
}
visited[nextBox][boxPos] = true
queue = append(queue, [2]int{nextBox, boxPos})
}
}
queue = queue[size:]
pushes++
}
return -1
}
func canPushBoxReach(grid [][]byte, start int, target int, box int) bool {
rows := len(grid)
cols := len(grid[0])
visited := make([]bool, rows*cols)
queue := []int{start}
visited[start] = true
for head := 0; head < len(queue); head++ {
pos := queue[head]
if pos == target {
return true
}
row := pos / cols
col := pos % cols
for _, direction := range pushBoxDirections {
nextRow := row + direction[0]
nextCol := col + direction[1]
if !isPushBoxOpen(grid, nextRow, nextCol) {
continue
}
next := nextRow*cols + nextCol
if next == box || visited[next] {
continue
}
visited[next] = true
queue = append(queue, next)
}
}
return false
}
func isPushBoxOpen(grid [][]byte, row int, col int) bool {
return row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) && grid[row][col] != '#'
}
复杂度分析
- 时间复杂度：$O((mn)^3)$。状态空间是「箱子位置 × 人位置」共 $O((mn)^2)$ 个，每个状态最多展开 4 个方向，而每次展开在通过去重后要跑一次 $O(mn)$ 的可达性 BFS，三者相乘即得。$m, n \le 20$ 时 $mn \le 400$，这个上界是极度悲观的估计——实际能被推到的箱子位置远少于 $mn$ 个，且大部分方向会被去重或墙提前挡掉。
- 空间复杂度：$O((mn)^2)$。主要开销是
visited这张 $mn \times mn$ 的布尔表，$400 \times 400$ 约 16 万字节，完全可接受；队列在最坏情况下也只装得下这么多状态，可达性 BFS 内部那份一维标记只有 $O(mn)$，被主表吞没。
关键点总结
- 代价函数决定搜索的层次划分。题目按推动计费，走路免费，所以 BFS 的一层必须是一次推动，而不是一次移动。见到「某类动作免费、另一类收费」的最短路问题，第一反应应该是 0-1 BFS 或者把 0 权边折叠成可达性判定，这两条路本题都能走通。
- 状态要覆盖所有影响后继的信息。只记箱子位置会丢掉「人在哪一侧」，导致后继集合算错。判断状态是否完整的标准很简单：给定这个状态，能否唯一确定它的合法转移集合。
- 把二维坐标压成一维下标是网格搜索的通用手法，让
visited退化成朴素数组，省掉哈希开销，也让状态相等判断变成整数比较。- 贵的检查放在便宜的检查后面。可达性 BFS 比数组查表贵三个数量级，先做去重和越界墙体判断能砍掉绝大多数调用，这是本题能在时限内跑过的实际原因。
- 面试视角：这题真正被考察的不是会不会写 BFS，而是能不能把「人的自由移动」正确地建模成零代价。面试时先把状态定义
(箱子, 人)和「一层 = 一次推动」这两句话说出来，再动手写；被追问优化时，可以主动提出「用 0-1 BFS 把走路和推动放进同一个双端队列」作为等价方案，或者提「可达性结果可以按箱子位置缓存复用」作为常数优化。
易错点总结
- 错误写法：只用
visited[boxPos]一维去重 → 在上面那张图里，箱子第一次到达(2,2)时人在(2,3)，之后即使存在「人在(2,1)侧、箱子同样在(2,2)」的局面也会被误判为访问过而剪掉，某些图上会直接返回 -1。- 错误写法：新状态写成
(nextBox, playerPos)→ 把人的位置留在了推动之前的地方。在走查的第 2 层，人本应在(2,1)，却被记成(2,2)，下一次可达性判定的起点就错了，能推出人根本到不了的路线。- 错误写法：
canReach里不把boxPos当障碍 → 等于允许人穿箱而过。当箱子正好堵住唯一走廊时，会认为人可以瞬间出现在箱子另一侧，算出比真实答案更小的推动次数。- 错误写法：站位算成
(boxRow + d0, boxCol + d1)，和落点同侧 → 变成了人站在箱子前方「拉」箱子，四个方向的判定全部反向，示例里第一次向左推会被判为需要人站在(2,2)，结果整体答案偏大甚至返回 -1。- 错误写法：
while里直接for (int[] s : queue)或不缓存size→ 本轮新入队的状态被当成同层处理，pushes只会加一次，示例的答案会退化成 1。- 错误写法：在入队时判断
nextBox == target并返回pushes→ 少算了一次推动，走查中第 2 层入队((1,1), (2,1))时会返回 2 而不是 3；而且箱子初始就在目标的用例会漏判。- 错误写法：等出队时才标记
visited→ 同一层里多个前驱都能推出同一个新状态，队列被塞入大量重复项，状态数爆炸后超时。- 错误写法：把
T或S所在格子当成不可通行 → 目标格是空地，箱子必须能被推上去；只排除#才是对的，写成grid[row][col] == '.'会让示例直接返回 -1。- 错误写法：
visited开成boolean[rows][cols]或只有total个元素的一维数组 → 维度对不上状态定义，运行时越界或去重语义错误。- 错误写法：把人的走路步数也累加进答案 → 走查第 2 层那次绕行 8 步会被记成 8 次代价，最终输出 11 而不是 3。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 773. 滑动谜题 | 困难 | 同样是把整个局面编码成状态做 BFS，但状态是棋盘排列的字符串，无需嵌套可达性判定 |
| 752. 打开转盘锁 | 中等 | 抽象状态图上的最短步数，转移集合固定为 8 种，难点在死亡数字剪枝而非状态设计 |
| 1293. 网格中的最短路径 | 困难 | 状态同样要加一维「剩余消除次数」，是本题「状态需超出坐标」思路的另一个范例 |
| 847. 访问所有节点的最短路径 | 困难 | 状态为「当前点 + 已访问集合的位掩码」，允许重复访问，去重靠状态而非节点 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 纯网格 BFS，状态就是坐标本身，可用来对照体会本题为何必须扩状态 |
| 490. 迷宫 | 中等 | 球一直滚到撞墙才停，转移不是一格而是一整段，考察「一次转移的粒度」怎么定义 |
| 994. 腐烂的橘子 | 中等 | 多源分层 BFS，层数即分钟数，是本题「一层 = 一个单位代价」的最简形态 |