X

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

题目大意:

推箱子

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

游戏地图用大小为 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-解题思路分析/
Categories: leetcode
kwantong: