1210：穿过迷宫的最少移动次数（2022 分）

力扣第 156 场周赛第 4 题

题目

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

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

分析

• 典型的 bfs，注意每种移动是否合法即可
• 用 (i,j,0/1) 代表蛇尾在格子 (i,j) 且处于水平/竖直状态

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        Q, vis = deque([(0,0,0,0)]), {(0,0,0)}
        while Q:
            w,i,j,p = Q.popleft()
            if (i,j,p)==(n-1,n-2,0):
                return w
            for x,y,q in [(i+1,j,p),(i,j+1,p),(i,j,p^1)]:
                x2,y2 = (x+1,y) if q else (x,y+1)
                if 0<=x2<n and 0<=y2<n and grid[x][y]==0==grid[x2][y2]:
                    if (x,y,q) not in vis and (q==p or grid[x+1][y+1]==0):
                        Q.append((w+1,x,y,q))
                        vis.add((x,y,q))
        return -1

99 ms