题目大意：
推箱子
「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 n * m 的网格 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
示例 4：
输入：grid = [["#","#","#","#","#","#","#"], ["#","S","#",".","B","T","#"], ["#","#","#","#","#","#","#"]] 输出：-1
提示：
- 1 <= grid.length <= 20
- 1 <= grid[i].length <= 20
- grid 仅包含字符 ‘.’, ‘#’, ‘S’ , ‘T’, 以及 ‘B’。
- grid 中 ‘S’, ‘B’ 和 ‘T’ 各只能出现一个。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1263
解题思路分析：
这是一道相对复杂的dfs题目。我们详细来分析一下。首先想推动箱子，人必须在箱子的相邻格子，同时箱子的反方向的格子是可自由行走区域。换句话说，如果想横向推动箱子一格，那么必须保证箱子所在位置的左右两格都是空地「.」，一个格子用来站人，另一个格子是箱子要推向的区域。同理，当要纵向推动箱子时，箱子的上下两个也要保证是空地。这是能推动箱子的第一个必要条件。否则箱子将无法横向或者纵向移动。
此外，当箱子的位置能保证相邻两格为空地时，还需要看推箱人是否能够走到空地处。如果人能够移动到箱子左侧，代表可以向右推箱子，如果人可以走到箱子上方，则代表可以向下推箱子。向左和向上推箱子也同理。这时能够推动箱子的第二个必要条件。
以上2个条件只要一个不满足，即无法完成箱子的移动。解题时，我们先看箱子可能存在的移动方向，理论上，上下左右四个方向都具有潜在的可能性，不过根据条件1，我们先看箱子左右两格是否都为空地（既不是障碍物，也不是地图边缘），如果是，则代表箱子有可能可以向左右两格方向移动，然后再看条件2，人所在的当前位置，是否能够移动到箱子左右两边，如果能，则代表箱子确实可以移动，反之则不行。注意，人在移动时，不仅要躲避障碍物，还要躲避箱子所在的位置。向下两格可以移动的条件同理。在判断出当前箱子可以移动的方向之后，可以开始dfs，将箱子移动到下一格，同时人移动到原先箱子的位置。直到箱子可以移动到目的地为止。dfs找到一个最短路径即是返回结果。
实现代码：
boolean[][][][]visited; // 用于记录访问过的结点
Integer[][][][]memo; // 记忆数组
int width, height; // 地图的宽和高
// dfs的四个方向
int[][] direcitons = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public int minPushBox(char[][] grid) {
width=grid[0].length; // 地图宽
height=grid.length; // 地图高
// 初始化访问数组
visited=new boolean[height][width][height][width];
// 初始化记忆数组
memo=new Integer[height][width][height][width];
// 先找到箱子所在的位置(br,bc)和人所在的位置(sr,sc)
int br=0, bc=0, sr=0, sc=0;
for(int i=0;i<height;i++){
for(int j=0;j<width;j++){
if(grid[i][j]=='B'){
br=i;
bc=j;
}else if(grid[i][j]=='S'){
sr=i;
sc=j;
}
}
}
// 开始dfs推箱子，找到最短路径
int res = dfs(br,bc,sr,sc,grid);
return res==400?-1:res;
}
// dfs的返回结果代表人在(sr,sc)时，
// 将箱子从(br,bc)推到目的地所需的最短路径
int dfs(int br,int bc,int sr,int sc,char[][] grid){
// 如果箱子在目的地上，无需操作，返回0
if(grid[br][bc]=='T'){
return 0;
}
// 如果记忆数组不为空，直接返回
if(memo[br][bc][sr][sc]!=null){
return memo[br][bc][sr][sc];
}
// 记录当前点已被访问过
visited[br][bc][sr][sc]=true;
int res=400; // 返回结果，初始化为最大值
// 箱子上下两格为空地时
if(br+1<height&&grid[br+1][bc]!='#'&&br-1>=0&&grid[br-1][bc]!='#'){
// 如果箱子没有从当前位置向上推动过，并且人能够移动到箱子下方
if(!visited[br-1][bc][br][bc]
&&canPlayerMove(sr,sc,br+1,bc,br,bc,new boolean[height][width],grid)){
// dfs向上移动箱子一格，人移动到原先箱子位置
res= Math.min(res, 1+dfs(br-1,bc,br,bc,grid));
}
// 如果箱子没有从当前位置向下推动过，并且人能够移动到箱子上方
if(!visited[br+1][bc][br][bc]
&&canPlayerMove(sr,sc,br-1,bc,br,bc,new boolean[height][width],grid)){
// dfs向下移动箱子一格，人移动到原先箱子位置
res= Math.min(res, 1+dfs(br+1,bc,br,bc,grid));
}
}
// 箱子左右两格为空地时
if(bc+1 < width && grid[br][bc+1]!='#'
&& bc-1 >= 0 && grid[br][bc-1]!='#'){
// 如果箱子没有从当前位置向左推动过，并且人能够移动到箱子右方
if(!visited[br][bc-1][br][bc]
&&canPlayerMove(sr,sc,br,bc+1,br,bc,new boolean[height][width],grid)){
// dfs向左移动箱子一格，人移动到原先箱子位置
res= Math.min(res, 1+dfs(br,bc-1,br,bc,grid));
}
// 如果箱子没有从当前位置向右推动过，并且人能够移动到箱子左方
if(!visited[br][bc+1][br][bc]
&&canPlayerMove(sr,sc,br,bc-1,br,bc,new boolean[height][width],grid)){
// dfs向右移动箱子一格，人移动到原先箱子位置
res= Math.min(res, 1+dfs(br,bc+1,br,bc,grid));
}
}
// 还原访问记录。（否则会影响其他dfs线路）
visited[br][bc][sr][sc]=false;
// 将结果保存至记忆数组
memo[br][bc][sr][sc]=res;
return res;
}
// 判断人能否从当前位置(sr,sc)移动到目标位置(tr,tc)
// 这里同样使用到dfs
boolean canPlayerMove(int sr,int sc,int tr,int tc,int br,int bc,
boolean[][]visited,char[][] grid){
// 记录当前位置已经访问过
visited[sr][sc]=true;
// 如果到达目标位置，返回true
if(sr==tr&&sc==tc){
return true;
}
// 以下是标准的四方向dfs操作
for(int[] direciton : direcitons){
int r=direciton[0]+sr,c=direciton[1]+sc;
if(r>=0&&c>=0&&r<height&&c<width
&&grid[r][c]!='#'&&!visited[r][c]&&(r!=br||c!=bc)){
if(canPlayerMove(r,c,tr,tc,br,bc,visited,grid)){
return true;
}
}
}
return false;
}本题解法执行时间为12ms。
Runtime: 12 ms, faster than 94.12% of Java online submissions for Minimum Moves to Move a Box to Their Target Location.
Memory Usage: 37.5 MB, less than 100.00% of Java online submissions for Minimum Moves to Move a Box to Their Target Location.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1263-minimum-moves-to-move-a-box-to-their-target-location-解题思路分析/