1. LeetCode 1263 推箱子问题解析推箱子Sokoban是一款经典的益智游戏玩家需要将箱子推到指定位置。在LeetCode 1263题中我们需要实现一个算法来计算将箱子推到目标位置所需的最少推动次数。这道题被标记为Hard难度主要考察对BFS算法的灵活运用和状态空间的处理能力。游戏的基本规则是玩家可以上下左右移动玩家可以推动箱子但不能拉动墙和边界会阻挡移动需要找到推动箱子的最短路径2. 问题建模与状态表示2.1 网格表示法游戏地图用二维字符数组grid表示其中# 代表墙. 代表空地S 代表玩家起始位置B 代表箱子起始位置T 代表目标位置我们需要设计一个状态表示方法能够同时记录玩家和箱子的位置。一个有效的状态应该包含三个要素玩家坐标 (px, py)箱子坐标 (bx, by)推动次数 count2.2 状态空间分析由于玩家和箱子的位置都会影响后续移动我们需要将两者的位置组合起来作为状态。对于m×n的网格理论上状态空间大小为O(m²n²)但实际上可达状态会少很多。关键观察点玩家必须能够到达推动箱子的位置每次推动都会改变箱子和玩家的位置不能重复访问相同状态3. 双BFS算法实现3.1 算法框架我们采用双层BFS的方法外层BFS处理箱子的移动内层BFS处理玩家能否到达推动位置public int minPushBox(char[][] grid) { int m grid.length, n grid[0].length; // 初始化玩家、箱子和目标位置 int[] player null, box null, target null; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] S) player new int[]{i, j}; else if (grid[i][j] B) box new int[]{i, j}; else if (grid[i][j] T) target new int[]{i, j}; } } // 使用优先队列按推动次数排序 PriorityQueueint[] queue new PriorityQueue((a, b) - a[4] - b[4]); queue.offer(new int[]{player[0], player[1], box[0], box[1], 0}); // 记录已访问状态 boolean[][][][] visited new boolean[m][n][m][n]; visited[player[0]][player[1]][box[0]][box[1]] true; int[][] dirs new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!queue.isEmpty()) { int[] cur queue.poll(); int px cur[0], py cur[1]; int bx cur[2], by cur[3]; int count cur[4]; if (bx target[0] by target[1]) { return count; } // 玩家尝试四个方向移动 for (int[] dir : dirs) { int nx px dir[0]; int ny py dir[1]; // 检查新位置是否合法 if (nx 0 || nx m || ny 0 || ny n || grid[nx][ny] #) { continue; } // 如果玩家移动到箱子位置则需要推动箱子 if (nx bx ny by) { int nbx bx dir[0]; int nby by dir[1]; if (nbx 0 || nbx m || nby 0 || nby n || grid[nbx][nby] #) { continue; } if (!visited[nx][ny][nbx][nby]) { visited[nx][ny][nbx][nby] true; queue.offer(new int[]{nx, ny, nbx, nby, count 1}); } } else { // 只是玩家移动不推动箱子 if (!visited[nx][ny][bx][by]) { visited[nx][ny][bx][by] true; queue.offer(new int[]{nx, ny, bx, by, count}); } } } } return -1; }3.2 算法优化上述基础实现可能会遇到性能问题我们可以进行以下优化优先队列优化使用优先队列确保总是扩展推动次数最少的状态双向BFS同时从初始状态和目标状态开始搜索启发式搜索加入曼哈顿距离等启发式函数引导搜索方向4. 关键实现细节4.1 状态判重处理使用四维数组visited[px][py][bx][by]记录已访问状态避免重复计算。这是算法正确性的关键保证。注意对于大型地图四维数组可能占用过多内存可以考虑使用哈希表存储已访问状态。4.2 推动与移动的区别玩家移动和推动箱子是两种不同的操作单纯移动不增加推动次数推动箱子会使推动次数1在代码中需要明确区分这两种情况。4.3 边界条件处理需要特别注意以下边界情况初始状态箱子已在目标位置目标位置被墙包围玩家无法到达推动位置网格尺寸为1×1的特殊情况5. 复杂度分析5.1 时间复杂度最坏情况下需要遍历所有可能的(px,py,bx,by)状态组合时间复杂度为O(m²n²)其中m和n是网格的行列数。5.2 空间复杂度主要消耗在存储已访问状态使用四维数组时为O(m²n²)使用哈希表时理论相同但常数更大。6. 实际编码技巧6.1 方向数组的使用使用dirs数组统一处理四个方向移动避免重复代码int[][] dirs {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 上、下、左、右6.2 状态压缩技巧对于较大的网格可以考虑将坐标压缩为单个整数来节省空间int encode(int x, int y) { return x * n y; }6.3 提前终止条件当箱子到达目标位置时可以立即返回不必继续搜索if (bx target[0] by target[1]) { return count; }7. 测试用例设计完整的解决方案应该能处理以下测试场景基本推动场景char[][] grid1 { {#,#,#,#,#}, {#,T,#,#,#}, {#,.,.,B,#}, {#,.,#,.,#}, {#,.,.,S,#}, {#,#,#,#,#} }; // 预期结果: 3无法完成的场景char[][] grid2 { {#,#,#,#,#}, {#,T,#,#,#}, {#,.,.,B,#}, {#,#,#,.,#}, {#,.,S,.,#}, {#,#,#,#,#} }; // 预期结果: -1初始位置即目标char[][] grid3 { {#,#,#,#,#}, {#,T,B,#,#}, {#,.,S,#,#}, {#,#,#,#,#} }; // 预期结果: 08. 常见错误与调试技巧8.1 无限循环问题如果忘记标记已访问状态可能导致无限循环。确保在加入队列前标记状态为已访问。8.2 推动次数计算错误注意区分玩家移动和推动箱子两种情况只有推动时才增加计数。8.3 边界检查顺序检查新位置合法性时应先检查数组越界再检查是否为墙避免数组越界异常。8.4 调试建议可以添加日志输出当前状态System.out.println(Player: (px,py), Box: (bx,by), Count: count);9. 算法扩展思考9.1 多箱子问题如果地图中有多个箱子需要推到各自目标位置问题将变得更加复杂可能需要使用A*算法等更高级的搜索策略。9.2 移动成本变化如果不同方向的移动或推动有不同的成本可以修改优先队列的比较函数来适应。9.3 实时解法对于需要实时响应的游戏场景可以预计算部分状态或使用更高效的启发式函数。在实际面试中遇到这类问题时建议先明确问题边界讨论状态表示方法再逐步实现基础版本最后讨论优化空间。推箱子问题很好地考察了对搜索算法的理解和实现能力是算法练习的经典题目。