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

ITCharge大约 5 分钟

---

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

标签：广度优先搜索、数组、矩阵
难度：困难

题目链接

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

题目大意

描述：给定一个 $n \times n$ 的网格 $grid$ 。网格中有一个长度为 $2$ 的蛇，蛇的初始位置是 $(0, 0)$ 和 $(0, 1)$ （水平放置），目标是到达右下角 $(n-1, n-2)$ 和 $(n-1, n-1)$ （水平放置）。

蛇可以执行三种操作：

向右移动：蛇身整体向右移动一格。
向下移动：蛇身整体向下移动一格。
旋转：蛇可以顺时针或逆时针旋转 $90^\circ$ 。旋转时，蛇的尾部（即旋转时保持不动的那个格子）在旋转过程中不能移动，且旋转路径不能有障碍物（墙）。

网格中 0 表示空地，1 表示障碍物。蛇身的任何部分都不能进入障碍物格子，也不能超出网格边界。

要求：返回蛇从初始位置到达目标位置所需的最少移动次数。如果无法到达，返回 $-1$ 。

说明：

$2 \le n \le 100$ 。

示例：

示例 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

解题思路

思路 1：BFS 状态搜索

1. 核心思想

蛇的长度固定为 $2$ ，关键信息是蛇的位置和朝向。可以用蛇的尾部坐标 $(x, y)$ 和方向 $dir$ 来表示蛇的完整状态（ $dir = 0$ 表示水平， $dir = 1$ 表示竖直）。

或者用蛇的两端坐标来表示：一个状态可以表示为 $(x_1, y_1, x_2, y_2)$ 。但由于蛇身只有两个格子且相邻，可以用 $(tail\_r, tail\_c, dir)$ 来更紧凑地表示状态，其中：

$dir = 0$ （水平）：蛇尾在 $(r, c)$ ，蛇头在 $(r, c+1)$ 。
$dir = 1$ （竖直）：蛇尾在 $(r, c)$ ，蛇头在 $(r+1, c)$ 。

目标状态是蛇尾在 $(n-1, n-2)$ ，蛇头在 $(n-1, n-1)$ ，方向水平。

2. 建图、遍历、标记、收集

建图：网格本身是图，空地是可通行的节点。
遍历：BFS 逐层遍历蛇的所有可能状态。
标记：用 $visited[tail\_r][tail\_c][dir]$ 标记某个状态是否已被访问过。
收集：当状态等于目标状态时，返回步数。

3. 三种操作的具体实现

向右移动（水平或竖直都适用，蛇尾为 $(r, c)$ ）：

水平：新状态 $(r, c+1, 0)$ ，要求 $(r, c+2)$ 是空地。
竖直：新状态 $(r, c+1, 1)$ ，要求 $(r, c+1)$ 和 $(r+1, c+1)$ 都是空地。

向下移动：

水平：新状态 $(r+1, c, 0)$ ，要求 $(r+1, c)$ 和 $(r+1, c+1)$ 都是空地。
竖直：新状态 $(r+1, c, 1)$ ，要求 $(r+2, c)$ 是空地。

旋转：

水平 → 竖直（顺时针旋转 $90^\circ$ ）：蛇尾 $(r, c)$ 不动，蛇头从 $(r, c+1)$ 转到 $(r+1, c)$ 。要求 $(r+1, c)$ 和 $(r+1, c+1)$ 都是空地。新状态 $(r, c, 1)$ 。
竖直 → 水平（逆时针旋转 $90^\circ$ ）：蛇尾 $(r, c)$ 不动，蛇头从 $(r+1, c)$ 转到 $(r, c+1)$ 。要求 $(r, c+1)$ 和 $(r+1, c+1)$ 都是空地。新状态 $(r, c, 0)$ 。

4. 具体步骤

第 1 步：初始化队列，将初始状态 $(0, 0, 0)$ （水平）入队， $visited[0][0][0] = True$ 。

第 2 步：BFS 分层遍历：

从队列中取出当前状态 $(r, c, dir)$ 和步数 $steps$ 。
如果达到目标状态 $(n-1, n-2, 0)$ ，返回 $steps$ 。
尝试三种操作，对每个合法且未访问过的新状态，入队并标记已访问。

第 3 步：队列为空则返回 $-1$ 。

5. 结合示例走一遍（简化）

对于示例 1 的网格，蛇从 $(0,0,0)$ 水平出发，通过一系列右移、下移和旋转操作到达 $(4,4,0)$ （右下角水平状态），共 $11$ 步。详细走法略过，核心是 BFS 分层搜索保证了最短步数。

思路 1：代码

from collections import deque

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # visited[r][c][dir]: dir=0 水平，dir=1 竖直
        visited = [[[False] * 2 for _ in range(n)] for _ in range(n)]
        q = deque()
        # 初始状态：蛇尾 (0,0)，水平放置，步数 0
        q.append((0, 0, 0, 0))
        visited[0][0][0] = True

        while q:
            r, c, dir, steps = q.popleft()

            # 检查是否到达目标：蛇尾 (n-1, n-2)，水平
            if r == n - 1 and c == n - 2 and dir == 0:
                return steps

            if dir == 0:  # 水平放置
                # 1. 向右移动
                if c + 2 < n and grid[r][c + 2] == 0 and not visited[r][c + 1][0]:
                    visited[r][c + 1][0] = True
                    q.append((r, c + 1, 0, steps + 1))
                # 2. 向下移动
                if r + 1 < n and grid[r + 1][c] == 0 and grid[r + 1][c + 1] == 0:
                    if not visited[r + 1][c][0]:
                        visited[r + 1][c][0] = True
                        q.append((r + 1, c, 0, steps + 1))
                    # 3. 旋转（水平 → 竖直）
                    # 蛇尾 (r,c) 不动，蛇头转到下面
                    # 需要 (r+1,c) 和 (r+1,c+1) 为空地
                    if not visited[r][c][1]:
                        visited[r][c][1] = True
                        q.append((r, c, 1, steps + 1))
            else:  # 竖直放置 (dir == 1)
                # 1. 向右移动
                if c + 1 < n and grid[r][c + 1] == 0 and grid[r + 1][c + 1] == 0:
                    if not visited[r][c + 1][1]:
                        visited[r][c + 1][1] = True
                        q.append((r, c + 1, 1, steps + 1))
                    # 3. 旋转（竖直 → 水平）
                    # 蛇尾 (r,c) 不动，蛇头转到右侧
                    # 需要 (r,c+1) 和 (r+1,c+1) 为空地
                    if not visited[r][c][0]:
                        visited[r][c][0] = True
                        q.append((r, c, 0, steps + 1))
                # 2. 向下移动
                if r + 2 < n and grid[r + 2][c] == 0 and not visited[r + 1][c][1]:
                    visited[r + 1][c][1] = True
                    q.append((r + 1, c, 1, steps + 1))

        return -1

思路 1：复杂度分析

时间复杂度： $O(n^2)$ ，每个状态 $(r, c, dir)$ 最多被访问一次，共有 $2 \times n \times n = O(n^2)$ 个状态，每次扩展常数次操作。
空间复杂度： $O(n^2)$ ，需要 $visited$ 数组和队列空间。