# LEETCODE 1263. Minimum Moves to Move a Box to Their Target Location 解题思路分析

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

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

```输入：grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]

```输入：grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#","#","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]

```输入：grid = [["#","#","#","#","#","#"],
["#","T",".",".","#","#"],
["#",".","#","B",".","#"],
["#",".",".",".",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]

```输入：grid = [["#","#","#","#","#","#","#"],
["#","S","#",".","B","T","#"],
["#","#","#","#","#","#","#"]]

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

```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;
}```

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.