题目

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).

Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

Example 1:

Input: 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]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: 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]]
Output: 9

Constraints:

2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.

解题思路

图的bfs求最短路径，注意旋转有前提即可

时间、空间复杂度$o(n^2)$

WA
case39一直过不了，我也没明白是为什么。。。肉眼看是有解的呀，不知道为什么正确答案是-1。。。

代码

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:

        def is_valid(grid, node1, node2) -> bool:
            n = len(grid)
            return 0 <= node1[0] < n and 0 <= node1[1] < n and 0 <= node2[0] < n and 0 <= node2[1] < n and grid[node1[0]][node1[1]] == 0 and grid[node2[0]][node2[1]] == 0

        import collections
        n = len(grid)
        queue = collections.deque([((0, 0), (0, 1), 0)])
        visited_spots = set()
        min_moves = -1
        while queue:
            node1, node2, path = queue.popleft()
            if node1 == (n - 1, n - 2) and node2 == (n - 1, n - 1):
                min_moves = min(min_moves if min_moves != -1 else 10000000, path)
            if (node1, node2) in visited_spots:
                continue
            visited_spots.add((node1, node2))
            # right
            new_node1, new_node2 = (node1[0], node1[1] + 1), (node2[0], node2[1] + 1)
            if is_valid(grid, new_node1, new_node2):
                queue.append((new_node1, new_node2, path + 1))
            # down
            new_node1, new_node2 = (node1[0] + 1, node1[1]), (node2[0] + 1, node2[1])
            if is_valid(grid, new_node1, new_node2):
                queue.append((new_node1, new_node2, path + 1))
            # rotate clockwise
            if node2[1] == node1[1] + 1:
                new_node1, new_node2 = (node1[0], node1[1]), (node2[0] + 1, node2[1] - 1)
                if is_valid(grid, new_node1, new_node2):
                    queue.append((new_node1, new_node2, path + 1))
            # rotate counterclockwise
            if node2[0] == node1[0] + 1:
                new_node1, new_node2 = (node1[0], node1[1]), (node2[0] - 1, node2[1] + 1)
                if is_valid(grid, new_node1, new_node2):
                    queue.append((new_node1, new_node2, path + 1))
        return min_moves