1210. 穿过迷宫的最少移动次数

这篇具有很好参考价值的文章主要介绍了1210. 穿过迷宫的最少移动次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

    1210. 穿过迷宫的最少移动次数

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

    1210. 穿过迷宫的最少移动次数

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

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

示例 1:

1210. 穿过迷宫的最少移动次数

输入: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
  • 蛇保证从空单元格开始出发。

类似于走迷宫,运动人物从占一个格变成占两个格,运动方向从上下左右变成左右旋转,使用广度优先遍历解决此类问题,在同一个位置有三种方式行动,每次行动又会有新的位置生成,生成新的位置就会有新的运动路径(即三种方式)。使用队列将每次的三种方式都走一遍后将新的位置结点放入队列,并记录当前运动次数。直到循环结束,返回结果。

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);
            }
        }
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        dist[0][0][0] = 0;
        //队列中放入位置和当前横竖状态
        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});
                }
            }
        }
        //返回移动次数,如果没有到达则会返回一个数组的初始化值-1
        return dist[n-1][n-2][0];
    }
}

 动态规划

力扣文章来源地址https://www.toymoban.com/news/detail-433199.html

到了这里,关于1210. 穿过迷宫的最少移动次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 输入单词需要的最少按键次数 I

    输入单词需要的最少按键次数 I 1 = word.length = 26 word 仅由小写英文字母组成 word 中的所有字母互不相同 因为word 中的所有字母互不相同,可以以任意8个字符为一组,第一组每个字符需要按键一次,第二组需要按键两次,以此类推…根据字符串长度将每组字符的按键次数累加起

    2024年01月24日
    浏览(42)
  • 题目:2027.转换字符串的最少操作次数

    ​​ 题目来源:         leetcode题目,网址:2027. 转换字符串的最少操作次数 - 力扣(LeetCode) 解题思路:        遍历字符串,如果当前位置字符是 \\\'X\\\',计数加一并将当前元素及其后面的元素变为\\\'0\\\',然后继续遍历字符串。最后返回计数结果即可。 解题代码: 总结:  

    2024年02月16日
    浏览(40)
  • C++二分算法:得到子序列的最少操作次数

    二分查找算法合集 给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arr ,arr 可能 包含重复元素。 每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2] ,那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后

    2024年02月05日
    浏览(45)
  • 【算法题】2602. 使数组元素全部相等的最少操作次数

    给你一个正整数数组 nums 。 同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中,你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次: 将数组里一个元素 增大 或者 减小 1 。 请你返回一个长度为 m 的数组 answer ,其中 answer[i]是将 nums 中所有元素变成

    2023年04月24日
    浏览(35)
  • 【LeetCode - 每日一题】1654. 到家的最少跳跃次数(23.08.30)

    可以左跳可以右跳 不能连续左跳两次 不能跳到负数 不能跳到 forbidden[] 求可以跳到 x 的最少跳跃次数 a. overview 最初时,只有 0 位置可以进行跳跃;在跳到 a 位置后,又可以跳到 2a 位置和 a-b 位置(如果 ab );然后又多了两个位置(或者一个位置)可以跳跃…因此这是一个

    2024年02月10日
    浏览(46)
  • 【状态机dp 动态规划】100290. 使矩阵满足条件的最少操作次数

    动态规划汇总 状态机dp 给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中,你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后,你需要确保每个格子 grid[i][j] 的值满足: 如果下面相邻格子存在的话,它们的值相等,也就是 grid[i][j] == grid[i + 1][j](如果存在)

    2024年04月24日
    浏览(34)
  • 2023-06-17 LeetCode每日一题(分割圆的最少切割次数)

    点击跳转到题目位置 圆内一个 有效切割 ,符合以下二者之一: 该切割是两个端点在圆上的线段,且该线段经过圆心。 该切割是一端在圆心另一端在圆上的线段。 一些有效和无效的切割如下图所示。 给你一个整数 n ,请你返回将圆切割成相等的 n 等分的 最少 切割次数。

    2024年02月09日
    浏览(52)
  • 华为OD机考算法题:根据某条件聚类最少交换次数

    题目部分 解读与思路 代码实现 题目 根据某条件聚类最少交换次数 难度 难 题目说明 给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。 组合一起是指满足条件的数字相邻,不要求相邻后在数组中的位置。 数据范围 -100 =K = 100 -100 = 数组中数值 = 100 输入描

    2024年02月09日
    浏览(36)
  • Leetcode3071. 在矩阵上写出字母 Y 所需的最少操作次数

    题目来源:3071. 在矩阵上写出字母 Y 所需的最少操作次数 统计 Y 中的元素出现次数,记到一个长为 3 的数组 cnt1 中。统计不在 Y 中的元素出现次数,记到一个长为 3 的数组 cnt2 中。 计算最多可以保留多少个元素不变,设这个值为 maxNotChange。 在 0,1,2 中枚举 i 和 j,其中 i≠

    2024年03月18日
    浏览(47)
  • 两个有序表合并成一个有序表最少与最多的比较次数

    在数据结构(严蔚敏)第二章课后习题中有这样一个题,关于把两个有序表合并的操作比较次数 将两个各有 N 个元素的有序表归并成一个有序表,其最少的比较次数是( A )。 A.N B.2N -1 C.2N D.N -1 显然,比如A顺序表的最大值如果比B顺序表的最小值还要小,只需要拿B的最

    2024年02月10日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包