题目链接：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存储队列和存储距离的数组所需要使用的空间。