建设网站能解决什么问题/外包接单平台

难度困难105

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

• 玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
• 地板用字符 '.' 表示，意味着可以自由行走。
• 墙用字符 '#' 表示，意味着障碍物，不能通行。
• 箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
• 玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
• 玩家无法越过箱子。

返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

示例 1：

输入：grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#",".","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
输出：3
解释：我们只需要返回推箱子的次数。

示例 2：

输入：grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#","#","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
输出：-1

示例 3：

输入：grid = [["#","#","#","#","#","#"],["#","T",".",".","#","#"],["#",".","#","B",".","#"],["#",".",".",".",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
输出：5
解释：向下、向左、向左、向上再向上。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid 仅包含字符 '.', '#', 'S' , 'T', 以及 'B'。
• grid 中 'S', 'B' 和 'T' 各只能出现一个。

题解：https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/solution/tong-su-yi-dong-dai-ma-dai-zhu-shi-java-mi4f6/

试想一下，如果箱子可以自己移动(见鬼)，这道题目你会做吗？

这不就变成了一个简单的BFS吗？之所以用BFS而不是DFS，是因为使用BFS(层次化版本)可以一层一层向外扩展，从而轻易得到“最短移动步数”。

再思考，如果加入“箱子需要人从背后推动”的条件，会带来什么不同呢？

箱子的移动受到了限制——只有人可以到达箱子的背后时，箱子才能在这个特定方向进行移动。至于“人是否可以到达箱子的背后”，这个子问题又可以用一次DFS来解决。

由此，我们得到了第一个重要的思路：

以箱子的视角进行BFS(主问题)，以人的视角进行DFS(子问题)，后者是前者得以进行的前提。

想象一下，此时箱子正位于一个狭窄的“通道”内，这种情况下，人究竟是站在箱子的那一侧就尤为重要。换句话讲，箱子虽然位于同一位置，但人的位置不同，箱子其实仍处于不同的状态（请仔细琢磨“状态”这个用词）。

由此，引出了第二个重要的思路：

箱子的状态包含两个信息，箱子的位置、箱子的来源（它刚刚是以什么样的方向被推来的）。

而我们为什么要纠结于箱子的状态？

因为箱子在BFS时需要设置visited数组来防止重复（实际上防止死循环），而是否发生重复的依据正是箱子的状态。从代码的角度看，我们熟悉的visited数组长这个样子：boolean[][]，而现在它变成了这样：boolean[][][4]，4是指方向信息。

class Solution {//【BFS+DFS】以箱子的视角进行BFS,以人的视角进行DFS,后者作为前者得以进行的前提private final static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int minPushBox(char[][] grid) {int m = grid.length, n = grid[0].length;// 遍历一次，找出箱子起点/终点，人的初始位置int startX = -1;int startY = -1;int targetX = -1;int targetY = -1;int personX = -1;int personY = -1;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 'B') {startX = i;startY = j;}if (grid[i][j] == 'T') {targetX = i;targetY = j;grid[i][j] = '.';}if (grid[i][j] == 'S') {personX = i;personY = j;grid[i][j] = '.';}}}// 初始化队列，加入元素以启动BFSboolean[][][] visited = new boolean[m][n][4];Queue<Box> queue = new LinkedList<>();for(int i = 0; i < 4; i++){int[] d = directions[i];if (personCanReach(grid, m, n, personX, personY, startX - d[0], startY - d[1], new boolean[m][n])) {queue.add(new Box(startX, startY, i));visited[startX][startY][i] = true;}}// 以箱子的视角开始BFSint step = 0;while(!queue.isEmpty()){int size = queue.size();while(size-- > 0){Box box = queue.poll();grid[box.x][box.y] = 'B'; // 当前箱子的位置（人不能过）// 人在哪推的这一步？ 当箱子移动时需要判断人能否走到推动位置推动箱子personX = box.x - directions[box.from][0];personY = box.y - directions[box.from][1];if(box.x == targetX && box.y == targetY)return step;// BFS网格图遍历for(int i = 0; i < 4; i++){int[] d = directions[i];int nextX = box.x + d[0];int nextY = box.y + d[1];// 人是否能绕到箱子的后面？  (box.x, box.y)箱子当前位置，(box.x+d[0], box.y+d[1])箱子目标位置，(box.x-d[0], box.y-d[1])人推动箱子到目标位置的位置if (!personCanReach(grid, m, n, personX, personY, box.x - d[0], box.y - d[1], new boolean[m][n])) {continue;}// 箱子的下个位置是否合法？if (!isValid(grid, m, n, nextX, nextY)) {continue;}// 箱子的下一个状态是不是重复了？if(visited[nextX][nextY][i])continue;queue.add(new Box(nextX, nextY, i));visited[nextX][nextY][i] = true;}grid[box.x][box.y] = '.'; // 重置箱子的位置为地面，后面进行BFS还会弹出一个箱子位置}step += 1;}return -1;}// 人是否可以某一位置(startX, startY)到达另一位置(targetX, targetY)private boolean personCanReach(char[][] grid, int m, int n, int startX, int startY, int targetX, int targetY, boolean[][] visited) {if (startX == targetX && startY == targetY) {return true;}visited[startX][startY] = true;for (int[] direction : directions) {int nextX = startX + direction[0];int nextY = startY + direction[1];if (isValid(grid, m, n, nextX, nextY) && !visited[nextX][nextY]) {if (personCanReach(grid, m, n, nextX, nextY, targetX, targetY, visited)) {return true;}}}return false;}// 某位置是否可以踏足private boolean isValid(char[][] grid, int m, int n, int x, int y) {return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '.';}// 内部类，记录箱子位置、从哪个方向推过来的class Box{int x, y, from;public Box(int x, int y, int from){this.x = x;this.y = y;this.from = from;}}
}