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 1210. Minimum Moves to Reach Target with Rotations 解题思路分析

发表评论取消回复

站内搜索

近期文章

功能

站内搜索

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

发表评论 取消回复

站内搜索

近期文章

标签

功能

站内搜索

发表评论取消回复