【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp

简介: 思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1

穿过迷宫的最少移动次数【LC1210】


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


我们在一个 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))。


2d522877cf438a61401d21bbfbe30135.png


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


dd903fb1eb8ae8682ba57e4351398049.png


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


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


  • 思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1


。当status=0 时,需要考虑「向右移动」「向下移动」「顺时针旋转」三种情况

  • 「向右移动」:需要保证 (x,y+2) 是空的单元格;
  • 「向下移动」:需要保证(x+1,y) 和(x+1,y+1) 均是空的单元格;
  • 「顺时针旋转」:需要保证(x+1,y)和(x+1,y+1) 均是空的单元格。


。当 status=1 时,需要考虑「向右移动」「向下移动」「逆时针旋转」三种情况。

  • 「向右移动」:需要保证(x,y+1) 和(x+1,y+1) 均是空的单元格;
  • 「向下移动」:需要保证(x+2,y) 是空的单元格;
  • 「逆时针旋转」:需要保证(x,y+1) 和(x+1,y+1)均是空的单元格。


广度优先搜索方法的正确性在于:我们一定不会到达同一个位置两次及以上,因为这样必定不是最少的移动次数。


学习


  • 实现


。dist数组的含义


  • dist[x][y][0]表示当蛇尾坐标为(x,y),当蛇为水平时,达到这个位置的最短距离
  • dist[x][y][0]表示当蛇尾坐标为(x,y),当蛇为垂直时,达到这个位置的最短距离


class Solution {
    public int minimumMoves(int[][] grid) {
        int n = grid.length;
        int[][][] dist = new int[n][n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dist[i][j], -1);
            }
        }
        dist[0][0][0] = 0;
        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int x = arr[0], y = arr[1], status = arr[2];
            if (status == 0) {
                // 向右移动一个单元格
                if (y + 2 < n && dist[x][y + 1][0] == -1 && grid[x][y + 2] == 0) {
                    dist[x][y + 1][0] = dist[x][y][0] + 1;
                    queue.offer(new int[]{x, y + 1, 0});
                }
                // 向下移动一个单元格
                if (x + 1 < n && dist[x + 1][y][0] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0) {
                    dist[x + 1][y][0] = dist[x][y][0] + 1;
                    queue.offer(new int[]{x + 1, y, 0});
                }
                // 顺时针旋转 90 度
                if (x + 1 < n && y + 1 < n && dist[x][y][1] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0) {
                    dist[x][y][1] = dist[x][y][0] + 1;
                    queue.offer(new int[]{x, y, 1});
                }
            } else {
                // 向右移动一个单元格
                if (y + 1 < n && dist[x][y + 1][1] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) {
                    dist[x][y + 1][1] = dist[x][y][1] + 1;
                    queue.offer(new int[]{x, y + 1, 1});
                }
                // 向下移动一个单元格
                if (x + 2 < n && dist[x + 1][y][1] == -1 && grid[x + 2][y] == 0) {
                    dist[x + 1][y][1] = dist[x][y][1] + 1;
                    queue.offer(new int[]{x + 1, y, 1});
                }
                // 逆时针旋转 90 度
                if (x + 1 < n && y + 1 < n && dist[x][y][0] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) {
                    dist[x][y][0] = dist[x][y][1] + 1;
                    queue.offer(new int[]{x, y, 0});
                }
            }
        }
        return dist[n - 1][n - 2][0];
    }
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/minimum-moves-to-reach-target-with-rotations/solutions/2091767/chuan-guo-mi-gong-de-zui-shao-yi-dong-ci-pmnh/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


。复杂度


  • 时间复杂度:O ( n 2 )
  • 空间复杂度:O ( n 2 )


  • 优化:使用一份代码表示6种移动方式


。无论是水平状态还是竖直状态,蛇尾的状态变化为:


  • 向下移动:x 增加 1,y和 s 不变。用三元组 (1,0,0) 表示
  • 向右移动:y增加 1,x 和 s 不变。用三元组 (0,1,0) 表示
  • 旋转:s切换,即 0变为 1,1 变为 0;x 和 y不变。用三元组 (0,0,1) 表示


。蛇头的状态变化为


  • 如果s=0,蛇头在(x,y+1);如果 s=1,蛇头在(x+1,y)。也可以合并为一个公式表示蛇头:


(x+s,y+(s⊕1))


。实现时把这 3个三元组存到数组dirs中,遍历dirs,用同一份代码处理不同的移动,移动时需要判断:


  • 移动后蛇身不能出界
  • 移动后蛇身不能在障碍物上
  • 对于旋转,还需要保证 (x+1,y+1)没有障碍物


class Solution {
    private static int[][] DIRS = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    public int minimumMoves(int[][] g) {
        int n = g.length;
        var vis = new boolean[n][n][2];
        var q = new ArrayList<int[]>();
        vis[0][0][0] = true;
        q.add(new int[]{0, 0, 0}); // 初始位置
        for (int step = 1; !q.isEmpty(); ++step) {
            var tmp = q;
            q = new ArrayList<>();
            for (var t : tmp) {
                for (var d : DIRS) {
                    int x = t[0] + d[0], y = t[1] + d[1], s = t[2] ^ d[2];
                    int x2 = x + s, y2 = y + (s ^ 1); // 蛇头
                    if (x2 < n && y2 < n && !vis[x][y][s] &&
                        g[x][y] == 0 && g[x2][y2] == 0 && (d[2] == 0 || g[x + 1][y + 1] == 0)) {
                        if (x == n - 1 && y == n - 2) return step; // 此时蛇头一定在 (n-1,n-1)
                        vis[x][y][s] = true;
                        q.add(new int[]{x, y, s});
                    }
                }
            }
        }
        return -1;
    }
}
作者:灵茶山艾府
链接:https://leetcode.cn/problems/minimum-moves-to-reach-target-with-rotations/solutions/2093126/huan-zai-if-elseyi-ge-xun-huan-chu-li-li-tw8b/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


。复杂度


  • 时间复杂度:O ( n 2 )
  • 空间复杂度:O ( n 2 )
目录
相关文章
|
6月前
【每日一题Day114】LC1223 掷骰子模拟 | 记忆化搜索+dp
【每日一题Day114】LC1223 掷骰子模拟 | 记忆化搜索+dp
54 0
|
6月前
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
54 0
|
6月前
|
人工智能 BI
【每日一题Day267】LC834树中距离之和 | 换根dp
【每日一题Day267】LC834树中距离之和 | 换根dp
43 0
|
6月前
【每日一题Day244】LCP 41. 黑白翻转棋 bfs dfs
【每日一题Day244】LCP 41. 黑白翻转棋 bfs dfs
54 0
|
6月前
|
机器学习/深度学习
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
52 0
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
|
6月前
|
存储 人工智能 BI
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
52 0
|
6月前
|
存储 算法
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
45 0
|
6月前
【每日一题Day126】LC1140石子游戏Ⅱ | 博弈dp 记忆化搜索
【每日一题Day126】LC1140石子游戏Ⅱ | 博弈dp 记忆化搜索
47 0
|
机器学习/深度学习 人工智能
51nod 1055 最长等差数列 (dp好题)
51nod 1055 最长等差数列 (dp好题)
50 0
|
存储
Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_46618592/article/details/128890280?spm=1001.2014.3001.5501
115 0
Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)