LEETCODE 1210. Minimum Moves to Reach Target with Rotations 解题思路分析

题目大意:

穿过迷宫的最少移动次数

你还记得那条风靡全球的贪吃蛇吗?

我们在一个 n*n 的网格上构建了新的迷宫地图,蛇的长度为 2,也就是说它会占去两个单元格。蛇会从左上角((0, 0) 和 (0, 1))开始移动。我们用 0 表示空单元格,用 1 表示障碍物。蛇需要移动到迷宫的右下角((n-1, n-2) 和 (n-1, n-1))。

每次移动,蛇可以这样走:

・ 如果没有障碍,则向右移动一个单元格。并仍然保持身体的水平/竖直状态。
・ 如果没有障碍,则向下移动一个单元格。并仍然保持身体的水平/竖直状态。
・ 如果它处于水平状态并且其下面的两个单元都是空的,就顺时针旋转 90 度。蛇从((r, c)、(r, c+1))移动到 ((r, c)、(r+1, c))。

・ 如果它处于竖直状态并且其右面的两个单元都是空的,就逆时针旋转 90 度。蛇从((r, c)(r+1, c))移动到((r, c)(r, c+1))。

返回蛇抵达目的地所需的最少移动次数。

如果无法到达目的地,请返回 -1

示例 1:

输入:grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
  [0,0,0,0,1,1],
  [0,0,1,0,1,0],
  [0,1,1,0,0,0],
  [0,1,1,0,0,0]]
输出:11
解释:
一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。

示例 2:

输入:grid = [[0,0,1,1,1,1],
  [0,0,0,0,1,1],
  [1,1,0,0,0,1],
  [1,1,1,0,0,1],
  [1,1,1,0,0,1],
  [1,1,1,0,0,0]]
输出:9

提示:

  • 2 <= n <= 100
  • 0 <= grid[i][j] <= 1
  • 蛇保证从空单元格开始出发。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1210

解题思路分析:

看到格子,又看到求最短路径,应该下意识毫不犹豫的想到bfs广度优先搜索。本题虽然是Hard难度,但是与其他bfs题目比较起来换汤不换药,只不过把一个格子移动变成了两个,稍微升级了一点而已,解题思路大同小异。

如果对bfs不熟悉,可以参考我之前的文章 -> bfs相关题目讲解

我们先分析蛇可以移动的可能。

  • 当蛇处于水平姿势时,我们定义它所占据的两个格子的坐标为(row1, col1), (row2, col2),因为是在同一行上,因此row1等于row2。同时两格子相邻,col2等于col1+1。根据题意,水平时,蛇有三种移动的可能,向右平移,向下平移,或顺时针90度旋转。即:
// 水平向右移动一格
// 注意(row2, col2+1)在矩阵内且该点为0即可移动
(row1, col1), (row2, col2) ⇒ (row2, col2), (row2, col2+1) 
// 水平向下移动一格
// 注意(row1+1, col1)和(row2+1, col2)在矩阵内且该点为0即可移动
(row1, col1), (row2, col2) ⇒ (row1+1, col1), (row2+1, col2)
// 顺时针90度旋转
// 注意(row2+1, col2-1)在矩阵内且(row2+1, col2-1)和(row2+1, col2)为0即可移动
(row1, col1), (row2, col2) ⇒ (row1, col1), (row2+1, col2-1)
  • 当蛇处于垂直姿势时, 我们定义它所占据的两个格子的坐标为(row1, col1), (row2, col2), 因为是在同一列上,因此col1等于col2。同时两格子相邻,row2等于row1+1。根据题意,垂直时,蛇有三种移动的可能,向右平移,向下平移,或逆时针90度旋转。即:
// 水平向右移动一格
// 注意(row1, col1+1), (row2, col2+1)在矩阵内且该点为0即可移动
(row1, col1), (row2, col2) ⇒ (row1, col1+1), (row2, col2+1) 
// 水平向下移动一格
// 注意(row2+1, col2)在矩阵内且该点为0即可移动
(row1, col1), (row2, col2) ⇒ (row2, col2), (row2+1, col2)
// 逆时针90度旋转
// 注意(row2-1, col2+1)在矩阵内且(row2-1, col2+1)和(row2, col2+1)为0即可移动
(row1, col1), (row2, col2) ⇒ (row1, col1), (row2-1, col2+1)

总结起来大概分为以下几种情况:

搞清楚了移动条件之后,bfs本身并没有难度,代码中基本上是bfs的常规写法。最后需要注意一点,bfs要使用到visited数组记录已访问过的节点,避免重复搜索。这道题由于需要同时移动2个格子,因此,visited数组需要4维,visited[row1][col1][row2][col2]分别代表两个格子的坐标。考虑到执行效率问题,4维数组可以降维至3维,即: visited[row1][col1][row2] 即可。因为上文已经讲到过,两个格子是相邻的,在确定一个格子之后,另外一个格子要么在其下,要么在其右,只存在这两种可能,因此,第二个格子只要知道x坐标或者y坐标就能精确判断出其位置。故3维数组可行。

看下完整实现代码:

public int minimumMoves(int[][] grid) {
    int length=grid.length; // 矩阵边长
    if(grid[length-1][length-2] == 1 || grid[length-1][length-1]==1 ){
        return -1; // 如果终点是1,肯定走不通。
    }
    // 定义数组,记录已访问过的节点
    boolean[][][] visited = new boolean[length][length][length];
    Queue<int[]> q = new LinkedList<>(); // bfs用的Queue
    q.offer(new int[]{0,0,0,1}); // 将起点加入Queue
    visited[0][0][0]=true; // 设置起点以访问过
    int count=0; // 记录步数
    while(q.size()>0){ // Queue不为空就一直循环
        int size=q.size(); // 当前Queue的大小
        while(size-->0){ // 循环
            int[] current = q.poll(); // 取出一个元素
            // 得到该元素代表两个格子的坐标
            int r1=current[0],c1=current[1],r2=current[2],c2=current[3];
            // 如果该坐标与终点坐标相同,返回步数。
            if(r1==length-1&&c1==length-2&&r2==length-1&&c2==length-1){
                return count;
            }
            if(c1==c2){ // 蛇为垂直姿势
                if(r2+1<length && grid[r2+1][c1] != 1 && !visited[r2][c2][r2+1]){
                    // 向下垂直平移一格
                    q.offer(new int[]{r2,c2,r2+1,c2});
                    visited[r2][c2][r2+1]=true;
                }
                if(c1+1<length && grid[r1][c1+1] != 1 && grid[r2][c2+1] != 1){
                    if(!visited[r1][c1+1][r2]){
                        // 向右水平平移一格
                        q.offer(new int[]{r1,c1+1,r2,c2+1}); 
                        visited[r1][c1+1][r2]=true;
                    }
                    if(!visited[r1][c1][r2-1]){
                        visited[r1][c1][r2-1]=true;
                        // 逆时针90度旋转
                        q.offer(new int[]{r1,c1,r2-1,c2+1});
                    }
                }
            }else{ // 蛇为水平姿势
                if(c2+1<length && grid[r2][c2+1] != 1&&!visited[r2][c2][r2]){
                    // 向右水平平移一格
                    q.offer(new int[]{r2,c2,r2,c2+1});
                    visited[r2][c2][r2]=true;
                }
                if(r1+1<length && grid[r1+1][c1] != 1 && grid[r2+1][c2] != 1){
                    if(!visited[r1+1][c1][r2+1]){
                        // 向下垂直平移一格
                        q.offer(new int[]{r1+1,c1,r2+1,c2});
                        visited[r1+1][c1][r2+1]=true;
                    }
                    if(!visited[r1][c1][r2+1]){
                        visited[r1][c1][r2+1]=true;
                        // 顺时针90度旋转
                        q.offer(new int[]{r1,c1,r2+1,c2-1});
                    }
                }
            }
        }
        count++; // 步数加一
    }
    return -1;
}

本题解法执行时间为18ms。

Runtime: 18 ms, faster than 78.39% of Java online submissions for Minimum Moves to Reach Target with Rotations.

Memory Usage: 46.9 MB, less than 100.00% of Java online submissions for Minimum Moves to Reach Target with Rotations.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1210-minimum-moves-to-reach-target-with-rotations-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。