Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。https://blog.csdn.net/weixin_46618592/article/details/128890280?spm=1001.2014.3001.5501

在这里插入图片描述
题目链接:https://leetcode.cn/problems/minimum-moves-to-reach-target-with-rotations/description/

思路

题目的意思

可以把贪吃蛇的尾部看成一个点,要求从(0,0)到(n - 1, n - 2)的最短路径,但他并不是四个方向都能走,

  • 保持水平/垂直状态 向右或者向下走
  • 在水平状态下,可以顺时针旋转,并且保证 当前水平位置下边的两个格子都是存在的
  • 在垂直状态下,可以逆时针旋转,并且保证 当前垂直位置右边的两个格子都是存在的
碰到这种类型问题,需要看一下图的长度,这里在100以内,所以可以暴力用BFS或者DFS遍历答案,如果超过1000基本上是线性DP推导。

方法一:BFS遍历

用BFS遍历图,设置三元组{x, y , status}, status指状态,0 表示水平状态,1 表示竖直状态,点(x,y)需要考虑两种状态下的行动:

  • 水平状态下

    • 向右移动一个单元,保证(x, y + 2)格子为0.
    • 向下移动一个单元,保证(x + 1, y)和(x + 1, y + 1)格子为0.
    • 顺时针旋转,保证(x + 1, y)和(x + 1, y + 1)格子为0.
  • 垂直状态下

    • 向右移动一个单元,保证(x, y + 1)和(x + 1, y + 1)格子为0.
    • 向下移动一个单元,保证 (x + 2, y)格子为0.
    • 逆时针旋转,保证(x, y + 1)和(x + 1, y + 1)格子为0.
  • 他的例子都存在答案,所以不考虑-1的情况

代码示例

func minimumMoves(grid [][]int) int {
    n := len(grid)
    dist := make([][][2]int, n)
    for i := range dist {
        dist[i] = make([][2]int, n)
        for j := range dist[i] {
            dist[i][j] = [2]int{-1, -1}
        }
    }

    dist[0][0][0] = 0
    // 0 表示水平状态,1 表示竖直状态
    queue := [][3]int{{0, 0, 0}}
    for len(queue) > 0 {
        arr := queue[0]
        queue = queue[1:]
        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 = append(queue, [3]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 = append(queue, [3]int{x + 1, y, 0})
            }
            // 顺时针旋转
            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 = append(queue, [3]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 = append(queue, [3]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 = append(queue, [3]int{x + 1, y, 1})
            }
            // 逆时针旋转
            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 = append(queue, [3]int{x, y, 0})
            }
        }
    }
    return dist[n-1][n-2][0]
}

在这里插入图片描述

复杂度分析

  • 时间复杂度:O(n^2^),其中n表示图的长度和宽度,BFS遍历图需要O(n^2^)的时间。
  • 空间复杂度:O(n^2^),BFS存储队列和存储距离的数组所需要使用的空间。
目录
相关文章
|
15天前
【Leetcode 2583】二叉树中的第K大层和 —— 优先队列 + BFS
解题思路: - 使用队列保存节点,按层序依次保存该层节点 - 使用优先队列保存每层节点值的总和,最后剔除前k个大数即可得到
|
15天前
|
算法
leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)
leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)
35 0
|
15天前
|
机器学习/深度学习 存储
leetcode-1036:逃离大迷宫
leetcode-1036:逃离大迷宫
23 0
|
9月前
|
算法 安全 Android开发
LeetCode 周赛上分之旅 # 37 多源 BFS 与连通性问题
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
32 0
|
11月前
|
算法
从小白开始刷算法 bfs篇 leetcode.107
从小白开始刷算法 bfs篇 leetcode.107
从三道leetcode掌握广度优先搜索(BFS)
前言 BFS和DFS是如影随形的两种搜索方式,我们在上篇文章从三道leetcode掌握深度优先搜索(DFS)学习了递归的概念及DFS。不熟悉递归及DFS的同学可以先看看上篇文章,再阅读本篇比较好。
|
边缘计算 缓存 算法
LeetCode 双周赛 102,模拟 / BFS / Dijkstra / Floyd
昨晚是 LeetCode 双周赛第 102 场,你参加了吗?这场比赛比较简单,拼的是板子手速,继上周掉大分后算是回了一口血 😁。
89 0
LeetCode 102. 二叉树的层序遍历BFS
LeetCode 102. 二叉树的层序遍历BFS
60 0
LeetCode 102. 二叉树的层序遍历BFS
|
人工智能 Java BI
力扣207:课程表(Java拓扑排序:bfs+dfs)
力扣207:课程表(Java拓扑排序:bfs+dfs)
104 0
力扣200:岛屿数量(Java dfs+bfs)
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。