LeetCode 1263：推箱子
问题本质：推箱子的最小步骤
需将箱子（B）推到目标位置（T），玩家（S）可自由移动（避开墙和箱子），但推箱子必须站在旁边并向箱子方向推。目标是找到最小推动次数，若无法实现则返回 -1。
核心思路：双状态 BFS + 辅助可达性检查
1. 状态定义
每个状态由 箱子位置 (bx, by) 和玩家位置 (px, py) 组成，推动次数为当前步骤。通过 BFS 遍历状态，保证首次到达目标时的推动次数最小。
2. 关键观察
- 玩家移动时，箱子位置固定，需避开箱子（视为障碍）。
- 推箱子时，玩家必须站在箱子的反方向（如推箱子向上，玩家需站在箱子下方），推动后玩家移至箱子原位置。
3. 算法流程
- 定位初始状态：找到玩家、箱子、目标的坐标。
- 主 BFS：遍历所有可能的推箱子动作，记录状态和推动次数。
- 辅助 BFS：判断玩家在箱子固定时，能否从当前位置移动到推箱子所需的位置（反方向）。
算法步骤详解
步骤 1：定位初始位置
遍历网格，标记玩家（S）、箱子（B）、目标（T）的坐标：
int sx = -1, sy = -1, bx = -1, by = -1, tx = -1, ty = -1;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 'S') { sx = i; sy = j; }
else if (grid[i][j] == 'B') { bx = i; by = j; }
else if (grid[i][j] == 'T') { tx = i; ty = j; }
}
}
步骤 2：主 BFS 初始化
队列存储状态 [bx, by, px, py, moves]，访问集合避免重复处理：
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{bx, by, sx, sy, 0});
Set<String> visited = new HashSet<>();
visited.add(bx + "," + by + "," + sx + "," + sy);
步骤 3：推箱子的方向遍历
尝试四个方向（上、下、左、右）推动箱子，核心逻辑：
- 计算新状态：箱子新位置
(newBx, newBy)，玩家推前位置(pushPx, pushPy)（箱子反方向）。 - 合法性检查：新箱子位置需在网格内且非墙，推前位置需合法（非墙、在网格内）。
- 可达性检查：调用辅助 BFS，判断玩家能否从当前位置
(currPx, currPy)移动到推前位置(pushPx, pushPy)（避开当前箱子位置）。 - 状态更新：若合法且未访问，加入队列，推动次数
+1。
步骤 4：辅助 BFS（玩家可达性）
判断玩家在箱子位置 (blockX, blockY) 固定时，能否从 (startX, startY) 到达 (endX, endY)：
private boolean canReach(char[][] grid, int startX, int startY, int endX, int endY, int blockX, int blockY) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{startX, startY});
visited[startX][startY] = true;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!q.isEmpty()) {
int[] curr = q.poll();
int x = curr[0], y = curr[1];
if (x == endX && y == endY) return true;
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& !visited[nx][ny]
&& grid[nx][ny] != '#'
&& !(nx == blockX && ny == blockY)) { // 避开箱子
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
return false;
}
步骤 5：终止条件
若箱子到达目标位置，返回当前推动次数；队列空则返回 -1：
if (currBx == tx && currBy == ty) return moves;
完整代码（Java）
import java.util.*;
class Solution {
public int minPushBox(char[][] grid) {
int m = grid.length, n = grid[0].length;
int sx = -1, sy = -1, bx = -1, by = -1, tx = -1, ty = -1;
// 定位初始位置：S、B、T
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'S') { sx = i; sy = j; }
else if (grid[i][j] == 'B') { bx = i; by = j; }
else if (grid[i][j] == 'T') { tx = i; ty = j; }
}
}
// BFS队列：[bx, by, px, py, moves]
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{bx, by, sx, sy, 0});
Set<String> visited = new HashSet<>();
visited.add(bx + "," + by + "," + sx + "," + sy);
// 推动方向：上、下、左、右
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int currBx = curr[0], currBy = curr[1];
int currPx = curr[2], currPy = curr[3];
int moves = curr[4];
// 检查箱子是否到达目标
if (currBx == tx && currBy == ty) {
return moves;
}
// 尝试四个方向推动箱子
for (int[] dir : dirs) {
int dx = dir[0], dy = dir[1];
int newBx = currBx + dx, newBy = currBy + dy; // 箱子新位置
int pushPx = currBx - dx, pushPy = currBy - dy; // 玩家推前位置（反方向）
// 检查新箱子位置合法性：网格内、非墙
if (newBx < 0 || newBx >= m || newBy < 0 || newBy >= n) continue;
if (grid[newBx][newBy] == '#') continue;
// 检查推前位置合法性：网格内、非墙
if (pushPx < 0 || pushPx >= m || pushPy < 0 || pushPy >= n) continue;
if (grid[pushPx][pushPy] == '#') continue;
// 检查玩家能否从当前位置到达推前位置（避开当前箱子）
if (!canReach(grid, currPx, currPy, pushPx, pushPy, currBx, currBy)) {
continue;
}
// 推动后，玩家位置是箱子原位置
int newPx = currBx, newPy = currBy;
String key = newBx + "," + newBy + "," + newPx + "," + newPy;
// 新状态未访问则加入队列
if (!visited.contains(key)) {
visited.add(key);
queue.offer(new int[]{newBx, newBy, newPx, newPy, moves + 1});
}
}
}
// 无法到达目标
return -1;
}
// 辅助函数：判断玩家在箱子(blockX, blockY)处时，能否从(startX, startY)到(endX, endY)
private boolean canReach(char[][] grid, int startX, int startY, int endX, int endY, int blockX, int blockY) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{startX, startY});
visited[startX][startY] = true;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!q.isEmpty()) {
int[] curr = q.poll();
int x = curr[0], y = curr[1];
if (x == endX && y == endY) return true;
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& !visited[nx][ny]
&& grid[nx][ny] != '#'
&& !(nx == blockX && ny == blockY)) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
return false;
}
}
复杂度与优化
- 时间复杂度：
主 BFS 状态数为O((m×n)²)（箱子和玩家位置组合），每个状态调用辅助 BFS（O(m×n)），总复杂度为O((m×n)³)。对于m, n ≤ 20，计算量在可接受范围内。 - 空间复杂度：
队列和访问集合存储状态，空间复杂度为O((m×n)²)。
该算法通过 双状态跟踪 和 辅助可达性检查，精准模拟推箱子过程，确保最小推动次数的高效求解。核心在于将玩家移动与箱子推动解耦，利用 BFS 天然的最短路径特性，保证了算法的正确性与效率。