穿过迷宫的最少移动次数

难度: Hard

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

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

Submission

运行时间: 75 ms

内存: 18.4 MB

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n=len(grid)
        q=[(0,0,0,1,0)]
        visted=set((0,0,1,0))
        count=0
        while q:
            t=q
            q=[]
            for i,j,x,y,z in t:
                if i==n-1 and j==n-2 and x==n-1 and y==n-1:
                    return count
                if z==0:
                    if y+1<n and grid[x][y+1]==0 and (x,y,x,y+1) not in visted:
                        q.append((x,y,x,y+1,0))
                        visted.add((x,y,x,y+1))
                    if x+1<n and grid[i+1][j]==0 and grid[x+1][y] ==0:
                        if (i,j,i+1,j) not in visted:
                            q.append((i,j,i+1,j,1))
                            visted.add(((i,j,i+1,j)))
                        if (i+1,j,x+1,y) not in visted:
                            q.append((i+1,j,x+1,y,0))
                            visted.add((i+1,j,x+1,y))
                elif z==1:
                    if x+1<n and grid[x+1][y]==0 and (x,y,x+1,y) not in visted:
                        q.append((x,y,x+1,y,1))
                        visted.add((x,y,x+1,y))
                    if y+1<n and grid[x][y+1]==0 and grid[i][j+1]==0:
                        if (i,j,i,j+1) not in visted:
                            q.append((i,j,i,j+1,0))
                            visted.add((i,j,i,j+1))
                        if (i,j+1,x,j+1) not in visted:
                            q.append((i,j+1,x,j+1,1))
                            visted.add((i,j+1,x,j+1))
            count+=1
        print(count)
        return -1

Explain

该题解使用广度优先搜索（BFS）来寻找蛇从起点到终点的最短路径。每次搜索时，根据蛇的当前状态（水平或竖直）以及周围的障碍物情况，将下一步可能的移动状态加入队列中。同时使用一个集合 visted 来记录已访问过的状态，避免重复搜索。当搜索到达目标位置时，返回移动的次数 count。如果无法到达目标位置，则返回 -1。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = [(0, 0, 0, 1, 0)]  # 初始状态：(蛇头行, 蛇头列, 蛇尾行, 蛇尾列, 方向)
        visted = set((0, 0, 1, 0))  # 记录已访问过的状态
        count = 0  # 移动次数
        
        while q:
            t = q
            q = []
            for i, j, x, y, z in t:
                if i == n-1 and j == n-2 and x == n-1 and y == n-1:  # 到达目标位置
                    return count
                
                if z == 0:  # 水平状态
                    if y+1 < n and grid[x][y+1] == 0 and (x, y, x, y+1) not in visted:  # 向右移动
                        q.append((x, y, x, y+1, 0))
                        visted.add((x, y, x, y+1))
                    if x+1 < n and grid[i+1][j] == 0 and grid[x+1][y] == 0:  # 向下移动或顺时针旋转
                        if (i, j, i+1, j) not in visted:
                            q.append((i, j, i+1, j, 1))
                            visted.add((i, j, i+1, j))
                        if (i+1, j, x+1, y) not in visted:
                            q.append((i+1, j, x+1, y, 0))
                            visted.add((i+1, j, x+1, y))
                            
                elif z == 1:  # 竖直状态
                    if x+1 < n and grid[x+1][y] == 0 and (x, y, x+1, y) not in visted:  # 向下移动
                        q.append((x, y, x+1, y, 1))
                        visted.add((x, y, x+1, y))
                    if y+1 < n and grid[x][y+1] == 0 and grid[i][j+1] == 0:  # 向右移动或逆时针旋转
                        if (i, j, i, j+1) not in visted:
                            q.append((i, j, i, j+1, 0))
                            visted.add((i, j, i, j+1))
                        if (i, j+1, x, j+1) not in visted:
                            q.append((i, j+1, x, j+1, 1))
                            visted.add((i, j+1, x, j+1))
                            
            count += 1  # 移动次数加 1
        
        return -1  # 无法到达目标位置

Explore

在这种类型的路径搜索问题中，特别是寻找最短路径的场景，广度优先搜索（BFS）通常比深度优先搜索（DFS）更加适用。BFS以层级的方式扩展搜索范围，保证了一旦到达目标位置时，所经历的路径长度是最短的。相对地，DFS可能会沿着一个方向探索到底，即使找到目标位置，也不一定是最短路径。此外，对于大型网格，DFS由于其递归特性可能会遇到栈溢出的问题，而BFS则通常使用队列来实现，更适合处理这类问题。

五元组（i, j, x, y, z）中，i, j表示蛇头的位置，x, y表示蛇尾的位置，而z表示蛇的方向（0代表水平，1代表竖直）。这足以唯一标识蛇的状态，因为蛇的形状和方向完全由其头尾位置和方向决定。在此迷宫问题中，蛇的长度是固定的，且只能是水平或竖直，因此五元组能够准确记录并区分蛇在不同位置和方向的状态，避免重复搜索相同状态。

蛇的旋转操作确实有特定的条件限制。在算法中，蛇只能在没有障碍物阻碍的情况下旋转。例如，当蛇处于水平状态且准备顺时针旋转到竖直状态时，需要确保蛇头下方的格子以及蛇尾下方的格子都是空的（即没有障碍物）。这是因为旋转涉及到蛇头或蛇尾的移动到新位置，如果这些位置有障碍，则旋转不能执行。同样的逻辑适用于蛇从竖直状态旋转到水平状态时对右侧格子的检查。

是的，算法能够正确处理起始位置或目标位置被障碍物阻碍的情况并返回-1。在算法开始时，如果蛇的初始位置（头或尾）就被障碍物占据，蛇就无法开始移动，因此算法可以在初始检查阶段确认这一点。同样，如果在搜索过程中没有找到通往目标位置的有效路径，算法将在队列为空时结束循环，并返回-1，表示目标位置不可达。