What pattern does this problem follow?

It follows the Array plus Breadth-First Search pattern, tracking positions and orientations to compute minimal moves.

How do I handle rotations in the BFS?

Only perform rotations when the 2x2 area around the snake is empty, updating orientation and adding the new state to the queue.

What should I return if the snake cannot reach the target?

Return -1 if BFS completes without reaching the bottom-right target configuration.

What data structure is best for tracking visited states?

Use a set storing tuples of (head position, tail position, orientation) to efficiently avoid revisiting states.

Can GhostInterview show the exact moves sequence for Minimum Moves to Reach Target with Rotations?

Yes, it can generate the step-by-step move sequence, showing right, down, and rotation moves to reach the target efficiently.

#1210

Hard

auto_awesome图·搜索

LeetCode 题解工作台

穿过迷宫的最少移动次数

你还记得那条风靡全球的贪吃蛇吗？我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（ (0, 0) 和 (0, 1) ）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（ (n-1, n-2) 和 (n-1, n…

数组广度优先搜索矩阵

题目描述

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

我们在一个 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
蛇保证从空单元格开始出发。

lightbulb

解题思路

方法一：BFS

题目求的是蛇从起始位置到达目标位置的最少移动次数，我们考虑使用广度优先搜索 $BFS$ 来求解。

我们定义以下数据结构或变量：

队列 $q$ ：存储蛇的当前位置，每个位置是一个二元组 $(a, b)$ ，其中 $a$ 表示蛇的尾部位置，而 $b$ 表示蛇的头部位置。初始时，我们将位置 $(0, 1)$ 加入队列 $q$ 中。如果我们将二维迷宫扁平化成一个一维数组，那么位置 $(0, 1)$ 就表示一维数组下标为 $0$ 和 $1$ 的两个单元格。
目标位置 $target$ ：值固定为 $(n^2 - 2, n^2 - 1)$ ，即二维迷宫的最后一行的最后两个单元格。
数组或集合 $vis$ ：存储蛇的当前位置状态是否已经被访问过，每个状态是一个二元组 $(a, status)$ ，其中 $a$ 表示蛇的尾部位置；而 $status$ 表示蛇当前所处的状态，取值为 $0$ 或 $1$ ，分别表示蛇的水平状态和垂直状态。初始时将起始位置 $(0, 1)$ 的状态加入集合 $vis$ 中。
答案变量 $ans$ ：存储蛇从起始位置到达目标位置的移动次数，初始时为 $0$ 。

我们使用广度优先搜索来求解，每次从队列 $q$ 中取出一个位置，判断该位置是否为目标位置 $target$ ，如果是，则直接返回答案变量 $ans$ 。如果不是，则将该位置的下一个可能的位置加入队列 $q$ 中，并将该位置加入 $vis$ 中。注意，这里的下一个位置可能是蛇的水平状态或垂直状态，我们需要分别判断（具体见以下代码注释）。在每一轮搜索结束后，答案变量 $ans$ 自增 $1$ 。

最后，如果队列 $q$ 为空，说明无法从起始位置到达目标位置，返回 $-1$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是二维迷宫的行数或列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        def move(i1, j1, i2, j2):
            if 0 <= i1 < n and 0 <= j1 < n and 0 <= i2 < n and 0 <= j2 < n:
                a, b = i1 * n + j1, i2 * n + j2
                status = 0 if i1 == i2 else 1
                if (a, status) not in vis and grid[i1][j1] == 0 and grid[i2][j2] == 0:
                    q.append((a, b))
                    vis.add((a, status))

        n = len(grid)
        target = (n * n - 2, n * n - 1)
        q = deque([(0, 1)])
        vis = {(0, 0)}
        ans = 0
        while q:
            for _ in range(len(q)):
                a, b = q.popleft()
                if (a, b) == target:
                    return ans
                i1, j1 = a // n, a % n
                i2, j2 = b // n, b % n
                # 尝试向右平移（保持身体水平/垂直状态）
                move(i1, j1 + 1, i2, j2 + 1)
                # 尝试向下平移（保持身体水平/垂直状态）
                move(i1 + 1, j1, i2 + 1, j2)
                # 当前处于水平状态，且 grid[i1 + 1][j2] 无障碍，尝试顺时针旋转90°
                if i1 == i2 and i1 + 1 < n and grid[i1 + 1][j2] == 0:
                    move(i1, j1, i1 + 1, j1)
                # 当前处于垂直状态，且 grid[i2][j1 + 1] 无障碍，尝试逆时针旋转90°
                if j1 == j2 and j1 + 1 < n and grid[i2][j1 + 1] == 0:
                    move(i1, j1, i1, j1 + 1)
            ans += 1
        return -1

speed

复杂度分析

指标	值
时间	complexity is O(n^2 * 2) considering all positions and orientations. Space complexity is also O(n^2 * 2) for visited states and BFS queue storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate must correctly track snake orientation and positions separately.
question_mark
Look for BFS usage to ensure minimal moves are found instead of DFS.
question_mark
Check that rotations only occur when the required 2x2 space is empty.

warning

常见陷阱

外企场景

error
Failing to account for orientation when checking valid moves.
error
Forgetting to mark states as visited leading to cycles in BFS.
error
Attempting rotations without verifying all necessary cells are empty.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Snake length can be extended to more than 2 cells with similar BFS logic.
arrow_right_alt
Allow diagonal moves and rotations for more complex maneuvering.
arrow_right_alt
Introduce weighted moves where certain directions cost more, adjusting BFS to Dijkstra.

help

常见问题

外企场景

继续练习

#1254 统计封闭岛屿的数目 #1162 地图分析 #1263 推箱子