LeetCode 1263. 推箱子
题目描述
题意分析
玩家可以在空地上四向行走，但不能穿过墙或当前箱子。只有站在箱子后方，才能把它向前推一格；求送到目标位置所需的最少推动次数，无法送达时返回
-1。人绕行多少步不计入答案，所以不能把走路和推箱子都当成一次普通 BFS 移动。这里把任意次自由行走压缩成一次可达性检查，让主搜索只记录推动。
解法：按推箱子次数分层 BFS
核心思路
[!blue]
主状态是
(boxPos, playerPos)，两者都用row * cols + col编码。只记录箱子位置不够：箱子相同但人位于不同区域时，能够推动的方向可能不同。若要沿方向
(dr, dc)推动，箱子落点是(boxRow + dr, boxCol + dc)，人的站位是(boxRow - dr, boxCol - dc)。两处都必须在地图内且不是墙；此外，还要确认人能从当前位置走到站位，不能只看站位本身是不是空地。为此再做一次普通 BFS，把当前箱子位置视为额外障碍，其余非墙格都可走。这里只回答是否可达，不把走路步数加入答案。地图中的
B是最初的标记，箱子移动后应阻挡新的位置，旧B格可以再次经过。推动成功后，箱子进入落点，人进入箱子的旧位置，新状态固定为
(nextBox, boxPos)。每条主搜索边都恰好增加一次推动，因此按层 BFS，首次取出箱子到达目标的状态时，层数就是最少推动次数。用
visited[boxPos][playerPos]在入队时去重。相同状态之后的可推动方向完全相同，而 BFS 首次到达它的推动数最少，之后再到达无需重复展开。主队列耗尽仍未到目标，就说明不存在可行方案。
解题步骤
- 扫描地图找到
B、S、T，将初始双位置状态入队并标记，初始化pushes = 0。- 每轮先记录当前队列长度，只处理这一层的状态；若箱子已在目标上，返回
pushes。- 枚举四个推动方向，排除落点或站位不可走、结果状态已经访问的情况。
- 固定箱子不动，检查玩家能否到达所需站位；可达才把新状态标记并入队。
- 当前层处理完后让
pushes加一。全部状态搜索完仍未到达目标则返回-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(V^2)$，其中
V为格子数。除初始状态外，每次推动后人都在箱子四邻之一，所以实际主状态至多为4V + 1；每个状态最多进行四次 $O(V)$ 的站位检查。初始化完整访问表也需要 $O(V^2)$。- 空间复杂度：$O(V^2)$，当前实现分配箱子位置乘人位置的完整访问表。
关键点总结
[!green]
- 推完后人的位置是箱子旧位置，不是原来的远处位置。
- 当前箱子阻挡人行走，原来的 B 标记格并非永久障碍。
易错点总结
[!yellow]
- 只按箱子位置去重，会忽略人处于不同可达区域。
- 站位和落点放在同一侧，会变成拉箱子。
- 人的普通走动也计一层，会求成总动作最少而非推动最少。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1368. 使网格图至少有一条有效路径的最小代价 | 困难 | 步行可视为0费用、推箱为1费用，和原题的0/1边权类似，可用0-1 BFS组织搜索。 |
| 773. 滑动谜题 | 困难 | 同样搜索棋盘状态，本题需同时记录玩家和箱子位置，且优化推箱次数而不是总步数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！