推箱子【LC1263】
「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为
m x n的网格grid表示，其中每个元素可以是墙、地板或者是箱子。现在你将作为玩家参与游戏，按规则将箱子
'B'移动到目标位置'T'：
- 玩家用字符
'S'表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。- 地板用字符
'.'表示，意味着可以自由行走。- 墙用字符
'#'表示，意味着障碍物，不能通行。- 箱子仅有一个，用字符
'B'表示。相应地，网格上有一个目标位置'T'。
- 玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
- 玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。
新知识++
- 思路
简单情况：不需要玩家推动箱子，那么就是箱子位置到目标位置的最小移动次数，可以使用BFS搜索最短路径
本题需要玩家去推动箱子，因此需要记录玩家的位置，枚举玩家的移动方向，如果移动位置合法，那么判断是否移动了箱子以及移动后的箱子位置是否合法，如果玩家移动时推动了箱子，那么推动次数加1。【如果玩家移动后的位置等于箱子位置，那么表示推动了箱子】。当箱子到达了目标位置，就得到了最小推动次数。
在BFS时，需要记录三元组[ 箱子位置 , 玩家位置 , 推动次数 ] [箱子位置,玩家位置,推动次数][箱子位置,玩家位置,推动次数]，由于玩家在移动过程中，推动箱子的次数不一定增加，因此需要使用双端队列进行BFS(0-1BFS)，如果移动次数未增加那么将三元组放入队列的顶部，如果移动次数增加那么将三元组放入队列的末尾，保证先搜索小状态，后搜索大状态。
同时，为了避免重复访问，记录每种情况的访问状态
实现
class Solution { private int m; private int n; private char[][] grid; public int minPushBox(char[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int si = 0, sj = 0, bi = 0, bj = 0; // 找到玩家、箱子起始位置以及箱子目标位置 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 'S') { si = i; sj = j; } else if (grid[i][j] == 'B') { bi = i; bj = j; } } } int[] dirs = {-1, 0, 1, 0, -1}; Deque<int[]> q = new ArrayDeque<>(); boolean[][] vis = new boolean[m * n][m * n]; // 将初始三元组入队 q.offer(new int[] {f(si, sj), f(bi, bj), 0}); vis[f(si, sj)][f(bi, bj)] = true; while (!q.isEmpty()) { var p = q.poll(); int d = p[2]; bi = p[1] / n; bj = p[1] % n; // 箱子是否已经到目标位置 if (grid[bi][bj] == 'T') { return d; } si = p[0] / n; sj = p[0] % n; // 玩家移动 for (int k = 0; k < 4; ++k) { int sx = si + dirs[k], sy = sj + dirs[k + 1]; if (!check(sx, sy)) {// 非法 continue; } if (sx == bi && sy == bj) { int bx = bi + dirs[k], by = bj + dirs[k + 1]; if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {// 非法或者已经访问过 continue; } vis[f(sx, sy)][f(bx, by)] = true; q.offer(new int[] {f(sx, sy), f(bx, by), d + 1});// 箱子移动次数加1 } else if (!vis[f(sx, sy)][f(bi, bj)]) {// 没有访问过 vis[f(sx, sy)][f(bi, bj)] = true; q.offerFirst(new int[] {f(sx, sy), f(bi, bj), d});// 更新玩家位置 } } } return -1; } // 将二维坐标转化为一维坐标 private int f(int i, int j) { return i * n + j; } // 检查该位置是否越界或者是墙壁 private boolean check(int i, int j) { return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#'; } } 作者：ylb 链接：https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/solutions/2261099/python3javacgotypescript-yi-ti-yi-jie-sh-xgcz/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
