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.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        queue = deque([(0, 0, True)])
        dists = {(0, 0, True): 0}

        while queue:
            i, j, hor = queue.popleft()
            if (i, j) == (m-1, n-2):
                return dists[(i, j, hor)]
            if hor:
                if j+2 < n and not grid[i][j+2]:
                    if (i, j+1, hor) not in dists:
                        queue.append((i, j+1, hor))
                        dists[(i, j+1, hor)] = dists[(i, j, hor)]+1
                if i+1 < m and not grid[i+1][j] and not grid[i+1][j+1]:
                    if (i+1, j, hor) not in dists:
                        queue.append((i+1, j, hor))
                        dists[(i+1, j, hor)] = dists[(i, j, hor)]+1
                    if (i, j, not hor) not in dists:
                        queue.append((i, j, not hor))
                        dists[(i, j, not hor)] = dists[(i, j, hor)]+1
            else:
                if i+2 < m and not grid[i+2][j]:
                    if (i+1, j, hor) not in dists:
                        queue.append((i+1, j, hor))
                        dists[(i+1, j, hor)] = dists[(i, j, hor)]+1
                if j+1 < n and not grid[i][j+1] and not grid[i+1][j+1]:
                    if (i, j+1, hor) not in dists:
                        queue.append((i, j+1, hor))
                        dists[(i, j+1, hor)] = dists[(i, j, hor)]+1
                    if (i, j, not hor) not in dists:
                        queue.append((i, j, not hor))
                        dists[(i, j, not hor)] = dists[(i, j, hor)]+1
        
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = collections.deque([(0, 0, 0, 1, 0)])
        visited = set([(0, 0, 0, 1)])
        while q: 
            tailx, taily, headx, heady, steps = q.popleft()
            if (tailx == n-1 and taily == n-2 and headx == n-1 and heady == n-1):
                return steps
            for n_tailx, n_taily, n_headx, n_heady in (
                (tailx, taily+1, headx, heady+1),
                (tailx+1, taily, headx+1, heady)): 
                if (0 <= n_tailx < n and 0<= n_taily < n  and
                    0 <= n_headx < n and 0<= n_heady <n  and
                    (n_tailx, n_taily, n_headx, n_heady) not in visited and
                    grid[n_headx][n_heady] == 0 and grid[n_tailx][n_taily] == 0):
                    visited.add((n_tailx, n_taily, n_headx, n_heady))
                    #print(\"lr\", (n_tailx, n_taily, n_headx, n_heady, steps + 1)) 
                    q.append((n_tailx, n_taily, n_headx, n_heady, steps + 1))
            if (tailx == headx):
                if (tailx + 1 < n and 
                    grid[tailx + 1][taily] == 0 and 
                    grid[headx + 1][heady] == 0 and 
                    (tailx, taily, tailx+1, taily) not in visited):
                    visited.add((tailx, taily, tailx+1, taily))
                    #print(\"rc\",(tailx, taily, tailx+1, taily, steps + 1))
                    q.append((tailx, taily, tailx+1, taily, steps + 1))
            if (taily == heady):
                if (taily + 1 < n and 
                    grid[tailx][taily + 1] == 0 and 
                    grid[headx][heady +1] == 0 and 
                    (tailx, taily, tailx, taily+1) not in visited):
                    visited.add((tailx, taily, tailx, taily+1))
                    #print(\"rcc\",(tailx, taily, tailx, taily+1, steps + 1))
                    q.append((tailx, taily, tailx, taily+1, steps + 1))
                    
        return -1
                    
                    
            


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        start = (0, 0, 0, 1)
        end = (n - 1, n - 2, n - 1, n - 1)
        curr_level = {start}
        moves = 0
        visited = set()
        while curr_level:
            next_level = set()
            for pos in curr_level:
                visited.add(pos)
                r1, c1, r2, c2 = pos
                if c1 + 1 < n and grid[r1][c1+1] == 0 and c2 + 1 < n and grid[r2][c2+1] == 0:
                    if (r1, c1 + 1, r2, c2 + 1) not in visited:
                        next_level.add((r1, c1 + 1, r2, c2 + 1))
                        
                if r1 + 1 < n and grid[r1+1][c1] == 0 and r2 + 1 < n and grid[r2+1][c2] == 0:
                    if (r1 + 1, c1, r2 + 1, c1) not in visited:
                        next_level.add((r1 + 1, c1, r2 + 1, c2))
                        
                if r1 == r2 and c2 == c1 + 1 and r1 + 1 < n and grid[r1+1][c1] + grid[r1+1][c1+1] == 0 :
                    if (r1, c1, r1 + 1, c1) not in visited:
                        next_level.add((r1, c1, r1 + 1, c1))
                        
                if c1 == c2 and r2 == r1 + 1 and c1 + 1 < n and grid[r1][c1+1] + grid[r1+1][c1+1] == 0:
                    if (r1, c1, r1, c1 + 1) not in visited:
                        next_level.add((r1, c1, r1, c1 + 1))
                        
            if end in next_level:
                return moves + 1
            curr_level = next_level
            moves += 1
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        start = (0, 0, 0, 1)
        end = (n - 1, n - 2, n - 1, n - 1)
        curr_level = {start}
        moves = 0
        visited = set()
        while curr_level:
            next_level = set()
            for pos in curr_level:
                visited.add(pos)
                r1, c1, r2, c2 = pos
                if c1 + 1 < n and grid[r1][c1+1] == 0 and c2 + 1 < n and grid[r2][c2+1] == 0:
                    if (r1, c1 + 1, r2, c2 + 1) not in visited:
                        next_level.add((r1, c1 + 1, r2, c2 + 1))
                if r1 + 1 < n and grid[r1+1][c1] == 0 and r2 + 1 < n and grid[r2+1][c2] == 0:
                    if (r1 + 1, c1, r2 + 1, c1) not in visited:
                        next_level.add((r1 + 1, c1, r2 + 1, c2))
                if r1 == r2 and c2 == c1 + 1 and r1 + 1 < n and grid[r1+1][c1] + grid[r1+1][c1+1] == 0 :
                    if (r1, c1, r1 + 1, c1) not in visited:
                        next_level.add((r1, c1, r1 + 1, c1))
                if c1 == c2 and r2 == r1 + 1 and c1 + 1 < n and grid[r1][c1+1] + grid[r1+1][c1+1] == 0:
                    if (r1, c1, r1, c1 + 1) not in visited:
                        next_level.add((r1, c1, r1, c1 + 1))
            if end in next_level:
                return moves + 1
            curr_level = next_level
            moves += 1
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dq = collections.deque() # Front is left, back is right
        dq.append(((0,1),1,0,\"first move\")) # position of head, orientation, distance travelled
        seen = set()
        while len(dq) > 0:
            pos,orientation,dist,move = dq.popleft()
            # print(pos,orientation,dist,move,dq)
            i,j = pos
            if (pos,orientation) not in seen:
                seen.add((pos,orientation))
                if pos == (n-1,n-1):
                    if orientation == 1:
                        return dist
                    else:
                        pass
                else:
                    if orientation == 1:
                        if j < n - 1 and grid[i][j+1] == 0:
                            dq.append(((i,j+1),orientation,dist+1,\"go right\"))
                        if i < n - 1 and grid[i+1][j] == 0 and grid[i+1][j-1] == 0:
                            dq.append(((i+1,j),orientation,dist+1,\"go down\"))
                        if i < n - 1 and grid[i+1][j] == 0 and grid[i+1][j-1] == 0:
                            dq.append(((i+1,j-1),1-orientation,dist+1,\"rotate clockwise\"))
                    else:
                        if i < n - 1 and grid[i+1][j] == 0:
                            dq.append(((i+1,j),orientation,dist+1,\"go down\"))
                        if j < n - 1 and grid[i][j+1] == 0 and grid[i-1][j+1] == 0:
                            dq.append(((i,j+1),orientation,dist+1,\"go right\"))
                        if j < n - 1 and grid[i][j+1] == 0 and grid[i-1][j+1] == 0:
                            dq.append(((i-1,j+1),1-orientation,dist+1,\"rotate counterclockwise\"))
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        start = (0, 0, 0, 1)
        end = (n - 1, n - 2, n - 1, n - 1)
        curr_level = {start}
        moves = 0
        visited = set()
        while curr_level:
            next_level = set()
            for pos in curr_level:
                visited.add(pos)
                r1, c1, r2, c2 = pos
                if c1 + 1 < n and grid[r1][c1+1] == 0 and c2 + 1 < n and grid[r2][c2+1] == 0:
                    if (r1, c1 + 1, r2, c2 + 1) not in visited:
                        next_level.add((r1, c1 + 1, r2, c2 + 1))
                if r1 + 1 < n and grid[r1+1][c1] == 0 and r2 + 1 < n and grid[r2+1][c2] == 0:
                    if (r1 + 1, c1, r2 + 1, c1) not in visited:
                        next_level.add((r1 + 1, c1, r2 + 1, c2))
                if r1 == r2 and c2 == c1 + 1 and r1 + 1 < n and grid[r1+1][c1] + grid[r1+1][c1+1] == 0 :
                    if (r1, c1, r1 + 1, c1) not in visited:
                        next_level.add((r1, c1, r1 + 1, c1))
                if c1 == c2 and r2 == r1 + 1 and c1 + 1 < n and grid[r1][c1+1] + grid[r1+1][c1+1] == 0:
                    if (r1, c1, r1, c1 + 1) not in visited:
                        next_level.add((r1, c1, r1, c1 + 1))
            if end in next_level:
                return moves + 1
            curr_level = next_level
            moves += 1
        return -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        
        n = len(grid)
        q = [((0,1),(0,0))]
        visited = set(q)
        step = 0
        while q:
            l = len(q)
            for _ in range(l):
                (head, tail) = q.pop(0)
                # print(head, tail)
                if head==(n-1,n-1) and tail==(n-1,n-2): return step
                if head[1]>tail[1]:

                    if head[1]+1<n and grid[head[0]][head[1]+1]==0 and not ((head[0], head[1]+1), (tail[0],tail[1]+1)) in visited:
                        q.append(((head[0], head[1]+1), (tail[0],tail[1]+1))) # move right
                        visited.add(((head[0], head[1]+1), (tail[0],tail[1]+1)))
                    if head[0]+1<n and grid[head[0]+1][head[1]]+grid[tail[0]+1][tail[1]]==0: 
                        if not ((head[0]+1, head[1]), (tail[0]+1,tail[1])) in visited:
                            q.append(((head[0]+1, head[1]), (tail[0]+1,tail[1]))) # move down
                            visited.add(((head[0]+1, head[1]), (tail[0]+1,tail[1])))
                        if not ((head[0]+1,head[1]-1), tail) in visited:
                            q.append(((head[0]+1,head[1]-1), tail)) # rotate clockwise
                            visited.add(((head[0]+1,head[1]-1), tail))

                else: # h[1] == t[1]

                    if head[0]+1<n and grid[head[0]+1][head[1]] ==0 and not ((head[0]+1, head[1]), (tail[0]+1,tail[1])) in visited:
                        q.append(((head[0]+1, head[1]), (tail[0]+1,tail[1]))) # move down
                        visited.add(((head[0]+1, head[1]), (tail[0]+1,tail[1])))
                    if head[1]+1<n and grid[head[0]][head[1]+1]+grid[tail[0]][tail[1]+1]==0:
                        if not ((head[0], head[1]+1), (tail[0],tail[1]+1)) in visited:
                            q.append(((head[0], head[1]+1), (tail[0],tail[1]+1))) # move right
                            visited.add(((head[0], head[1]+1), (tail[0],tail[1]+1)))
                        if not ((head[0]-1,head[1]+1), tail) in visited:
                            q.append(((head[0]-1,head[1]+1), tail)) # rotate counterclockwise
                            visited.add(((head[0]-1,head[1]+1), tail))
            step += 1
                
            
        return -1
            
            
            
            


from collections import deque
class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        # shortest path = standard BFS
        n = len(grid)
        visited = {(0,1,0,0)}
        moves = -1
        queue = deque([(0,1, 0,0)]) # [curr, last]
        while queue:
            level_len = len(queue)
            moves +=1
            for _ in range(level_len):
                tp = queue.popleft()
                curr, last = tp[:2], tp[2:]
                if tp==(n-1,n-1,n-1,n-2):
                    return moves
                # 1. move right
                if curr[1]+1<n and last[1]+1<n and grid[curr[0]][curr[1]+1]==0 and grid[last[0]][last[1]+1]==0 and (curr[0], curr[1]+1, last[0], last[1]+1) not in visited:
                    visited.add((curr[0], curr[1]+1, last[0], last[1]+1))
                    queue.append((curr[0], curr[1]+1, last[0], last[1]+1))
                # 2. move down
                if curr[0]+1<n and last[0]+1<n and grid[curr[0]+1][curr[1]]==0 and grid[last[0]+1][last[1]]==0 and (curr[0]+1, curr[1], last[0]+1, last[1]) not in visited:
                    visited.add((curr[0]+1, curr[1], last[0]+1, last[1]))
                    queue.append((curr[0]+1, curr[1], last[0]+1, last[1]))
                # 3. rotate clockwise
                if curr[0]==last[0] and curr[0]+1<n and grid[curr[0]+1][curr[1]]==0 and grid[last[0]+1][last[1]]==0 and (curr[0]+1, curr[1]-1, last[0], last[1]) not in visited:
                    visited.add((curr[0]+1, curr[1]-1, last[0], last[1]))
                    queue.append((curr[0]+1, curr[1]-1, last[0], last[1]))
                # 4. rotate counterclockwise
                if curr[1]==last[1] and curr[1]+1<n and grid[curr[0]][curr[1]+1]==0 and grid[last[0]][last[1]+1]==0 and (curr[0]-1, curr[1]+1, last[0], last[1]) not in visited:
                    visited.add((curr[0]-1, curr[1]+1, last[0], last[1]))
                    queue.append((curr[0]-1, curr[1]+1, last[0], last[1]))
        return -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = collections.deque([(0, 0, 0, 1, 0)])
        visited = set()
        while q: 
            tailx, taily, headx, heady, steps = q.popleft()
            if (tailx, taily, headx, heady) in visited: continue
            visited.add((tailx, taily, headx, heady))
            if (tailx == n-1 and taily == n-2 and headx == n-1 and heady == n-1):
                return steps
            for n_tailx, n_taily, n_headx, n_heady in (
                (tailx, taily+1, headx, heady+1),
                (tailx+1, taily, headx+1, heady)): 
                if (0 <= n_tailx < n and 0<= n_taily < n  and
                    0 <= n_headx < n and 0<= n_heady <n  and
                    (n_tailx, n_taily, n_headx, n_heady) not in visited and
                    grid[n_headx][n_heady] == 0 and grid[n_tailx][n_taily] == 0):
                    #print(\"lr\", (n_tailx, n_taily, n_headx, n_heady, steps + 1)) 
                    q.append((n_tailx, n_taily, n_headx, n_heady, steps + 1))
            if (tailx == headx):
                if (tailx + 1 < n and 
                    grid[tailx + 1][taily] == 0 and 
                    grid[headx + 1][heady] == 0 and 
                    (tailx, taily, tailx+1, taily) not in visited):
                    #print(\"rc\",(tailx, taily, tailx+1, taily, steps + 1))
                    q.append((tailx, taily, tailx+1, taily, steps + 1))
            if (taily == heady):
                if (taily + 1 < n and 
                    grid[tailx][taily + 1] == 0 and 
                    grid[headx][heady +1] == 0 and 
                    (tailx, taily, tailx, taily+1) not in visited):
                    #print(\"rcc\",(tailx, taily, tailx, taily+1, steps + 1))
                    q.append((tailx, taily, tailx, taily+1, steps + 1))
                    
        return -1
                    
                    
            


class Solution:

    def minimumMoves(self, grid: List[List[int]]) -> int:
        visited = set()
        queue = deque()
        n = len(grid)
        queue.append((0, 0, 0, 1))
        visited.add(queue[0])
        res = 0
        target = (n-1, n-2, n-1, n-1)
        while queue:
            size = len(queue)
            for _ in range(size):
                curr = queue.popleft()
                if curr == target:
                    return res
                horizontal = curr[0] == curr[2]
                
                moves = []
                
                if curr[3] < n - 1 and grid[curr[0]][curr[1] + 1] == 0 and grid[curr[2]][curr[3] + 1] == 0:
                    moves.append((curr[0], curr[1] + 1, curr[2], curr[3] + 1))
                if curr[2] < n - 1 and grid[curr[0] + 1][curr[1]] == 0 and grid[curr[2] + 1][curr[3]] == 0:
                    moves.append((curr[0] + 1, curr[1], curr[2] + 1, curr[3]))
                if horizontal and curr[2] < n - 1 and grid[curr[0] + 1][curr[1]] == 0 and grid[curr[2] + 1][curr[3]] == 0:
                    moves.append((curr[0], curr[1], curr[0] + 1, curr[1]))
                if not horizontal and curr[3] < n - 1 and grid[curr[0]][curr[1] + 1] == 0 and grid[curr[2]][curr[3] + 1] == 0:
                    moves.append((curr[0], curr[1], curr[0], curr[1] + 1))
                
                for move in moves:
                    if move not in visited:
                        visited.add(move)
                        queue.append(move)
            res += 1
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        dq = deque([(0, 0, 0, 1)])
        seen = {(0, 0, 0, 1)}
        steps = 0
        
        while dq:
            length = len(dq)
            
            for _ in range(length):
                r0, c0, r1, c1 = dq.popleft()
                if r0==r1==M-1 and c0==N-2 and c1==N-1:
                    return steps
                
                if r0==r1:
                    # horizontal
                    # rotate clockwise
                    if r0+1<M and not grid[r0+1][c0] and not grid[r1+1][c1] \\
                        and (r0, c0, r0+1, c0) not in seen:
                        seen.add((r0, c0, r0+1, c0))
                        dq.append((r0, c0, r0+1, c0))
                elif c0==c1:
                    # vertical
                    # rotate counter clockwise
                    if c1+1<N and not grid[r0][c0+1] and not grid[r1][c1+1] \\
                        and (r0, c0, r0, c0+1) not in seen:
                        seen.add((r0, c0, r0, c0+1))
                        dq.append((r0, c0, r0, c0+1))
                
                # 1. move right
                if c1+1<N and not grid[r0][c0+1] and not grid[r1][c1+1] \\
                    and (r0, c0+1, r1, c1+1) not in seen:
                    seen.add((r0, c0+1, r1, c1+1))
                    dq.append((r0, c0+1, r1, c1+1))
                    
                # 2. move down
                if r1+1<M and not grid[r0+1][c0] and not grid[r1+1][c1] \\
                    and (r0+1, c0, r1+1, c1) not in seen:
                    seen.add((r0+1, c0, r1+1, c1))
                    dq.append((r0+1, c0, r1+1, c1))
                    
            steps += 1
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        stack = [(0, 0, 0, 0, 1)]
        n = len(grid)
        visited = set()
        visited.add((0, 0, 0, 1))

        while stack:
            stepNow, ia, ja, ib, jb = heapq.heappop(stack)
            
            ia1, ja1, ib1, jb1 = ia, ja+1, ib, jb+1
            if jb1 < n and grid[ib1][jb1] == 0 and grid[ia1][ja1] == 0 and (ia1, ja1, ib1, jb1) not in visited:
                if (ia1, ja1, ib1, jb1) == (n-1, n-2, n-1, n-1):
                    return stepNow+1
                visited.add((ia1, ja1, ib1, jb1))
                heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1))
            
            ia1, ja1, ib1, jb1 = ia+1, ja, ib+1, jb
            if ia1 < n and ib1 < n and grid[ib1][jb1] == 0 and grid[ia1][ja1] == 0 and (ia1, ja1, ib1, jb1) not in visited:
                if (ia1, ja1, ib1, jb1) == (n-1, n-2, n-1, n-1):
                    return stepNow+1
                visited.add((ia1, ja1, ib1, jb1))
                heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1))
            
            if ia == ib and ja == jb-1:
                if ia + 1< n and grid[ia+1][ja] == 0 and grid[ib+1][jb] == 0:
                    ia1, ja1, ib1, jb1 = ia, ja, ia+1, ja
                    if (ia1, ja1, ib1, jb1) not in visited:
                        if (ia1, ja1, ib1, jb1) == (n-1, n-2, n-1, n-1):
                            return stepNow+1
                        visited.add((ia1, ja1, ib1, jb1))
                        heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1)) 
            
            if ja == jb and ia == ib-1:
                if ja + 1 < n and grid[ia][ja+1] == 0 and grid[ib][jb+1] == 0:
                    ia1, ja1, ib1, jb1 = ia, ja, ia, ja+1
                    if (ia1, ja1, ib1, jb1) not in visited:
                        if (ia1, ja1, ib1, jb1) == (n-1, n-2, n-1, n-1):
                            return stepNow+1
                        visited.add((ia1, ja1, ib1, jb1))
                        heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1)) 
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        m = n = len(grid)
        visited = {0}
        @lru_cache(None)
        def move(i, j, k, r):
            if i == m - 1 and j == n - 1 and k == 0:
                return 0
            result = 1e9
            if k == 0:
                if j + 1 < n and grid[i][j + 1] != 1:
                    result = min(result, 1 + move(i, j + 1, k, 0))
                if i + 1 < m and grid[i + 1][j] != 1 and grid[i + 1][j - 1] != 1:
                    result = min(result, 1 + move(i + 1, j, k, 0))
                    if not r:
                        result = min(result, 1 + move(i + 1, j - 1, 1, 1)) 
            else:
                if i + 1 < m and grid[i + 1][j] != 1:
                    result = min(result, 1 + move(i + 1, j, k, 0))
                if j + 1 < n and grid[i][j + 1] != 1 and grid[i - 1][j + 1] != 1:
                    result = min(result, 1 + move(i, j + 1, k, 0))
                    if not r:
                        result = min(result, 1 + move(i - 1, j + 1, 0, 1))
            return result
        
        result = move(0, 1, 0, 0)
        return result if result < 1e9 else -1

class Solution:
    def is_empty(self, xy):
        if 0 <= xy[0] < self.m and 0 <= xy[1] < self.n: 
            return self.grid[xy[0]][xy[1]] == 0
        else:
            return False
    
    def next_positions(self, pos):
        tail, head = pos
        if tail[0] == head[0]:
            if self.is_empty((head[0], head[1] + 1)):
                yield head, (head[0], head[1] + 1)
            if self.is_empty((tail[0] + 1, tail[1])) and self.is_empty((head[0] + 1, head[1])):
                yield (tail[0] + 1, tail[1]), (head[0] + 1, head[1])
                yield tail, (tail[0] + 1, tail[1])
        else:
            assert tail[1] == head[1]
            if self.is_empty((head[0] + 1, head[1])):
                yield head, (head[0] + 1, head[1])
            if self.is_empty((tail[0], tail[1] + 1)) and self.is_empty((head[0], head[1] + 1)):
                yield (tail[0], tail[1] + 1), (head[0], head[1] + 1)
                yield tail, (tail[0], tail[1] + 1)
            
    def minimumMoves(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.m = len(grid)
        self.n = len(grid[0])
        
        layer = {((0, 0), (0, 1))}
        visited = set()
        dist = 0
        target = ((self.m - 1, self.n - 2), (self.m - 1, self.n - 1))
        
        while layer:
            if target in layer:
                return dist
            visited |= layer
            next_layer = set()
            for pos in layer:
                for next_pos in self.next_positions(pos):
                    if next_pos not in visited:
                        next_layer.add(next_pos)
            layer = next_layer
            dist += 1
        return -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = collections.deque([(0, 0, 0, 1, 0)])
        visited = {(0, 0, 0, 1)}
        while queue:
            r0, c0, r1, c1, steps = queue.popleft()
            print(r0, c0, r1, c1, steps)
            if r0 == n - 1 and r1 == n - 1 and c0 == n - 2 and c1 == n - 1:
                return steps
            if r0 == r1:
                if 0 <= c1 + 1 < n and not grid[r1][c1 + 1] and (r1, c1, r1, c1 + 1) not in visited:
                    visited.add((r1, c1, r1, c1 + 1))
                    queue.append((r1, c1, r1, c1 + 1, steps + 1))
                if 0 <= r0 + 1 < n and not grid[r0 + 1][c0] and not grid[r1 + 1][c1]:
                    if (r0 + 1, c0, r1 + 1, c1) not in visited:
                        visited.add((r0 + 1, c0, r1 + 1, c1))
                        queue.append((r0 + 1, c0, r1 + 1, c1, steps + 1))
                    if (r0, c0, r0 + 1, c0) not in visited:
                        visited.add((r0, c0, r0 + 1, c0))
                        queue.append((r0, c0, r0 + 1, c0, steps + 1))
            else:
                if 0 <= c0 + 1 < n and not grid[r0][c0 + 1] and not grid[r1][c1 + 1]:
                    if (r0, c0 + 1, r1, c1 + 1) not in visited:
                        visited.add((r0, c0 + 1, r1, c1 + 1))
                        queue.append((r0, c0 + 1, r1, c1 + 1, steps + 1))
                    if (r0, c0, r0, c0 + 1) not in visited:
                        visited.add((r0, c0, r0, c0 + 1))
                        queue.append((r0, c0, r0, c0 + 1, steps + 1))
                if 0 <= r1 + 1 < n and not grid[r1 + 1][c1]:
                    if (r1, c1, r1 + 1, c1) not in visited:
                        visited.add((r1, c1, r1 + 1, c1))
                        queue.append((r1, c1, r1 + 1, c1, steps + 1))
        
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
        num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]

        if not (grid[0][0] == grid[0][1] == 0):
            raise ValueError

        # initialization
        num_steps_horizontal[0][0] = 0
        for col in range(1, n - 1):
            if grid[0][col + 1] == 0:
                num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
            else:
                break

        # iterate over num_steps_horizontal and num_steps_vertical
        for row in range(n):
            for col in range(n):
                if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
                    num_steps_horizontal[row][col] = min(
                        num_steps_horizontal[row][col],
                        1 + num_steps_horizontal[row][col - 1], # from left 
                        1 + num_steps_horizontal[row - 1][col], # from above
                        )
                if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
                    num_steps_vertical[row][col] = min(
                        num_steps_vertical[row][col],
                        1 + num_steps_vertical[row][col - 1], # from left 
                        1 + num_steps_vertical[row - 1][col], # from above
                        )
                if (col < n - 1 and row < n - 1
                   and grid[row][col] == grid[row][col + 1] == 0
                   and grid[row + 1][col] == grid[row + 1][col + 1] == 0):
                    num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
                    num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
        
        if num_steps_horizontal[-1][-2] < float('inf'):
            return num_steps_horizontal[-1][-2]
        else:
            return -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        queue, visited, n = collections.deque([( (0, 0), (0, 1), 0)]), set(), len(grid)
        target = ((n-1, n-2), (n-1, n-1))
        while queue:
            (r1, c1), (r2, c2), steps = queue.popleft()
            if ((r1, c1), (r2, c2))==target:
                return steps
            if ((r1, c1), (r2, c2)) in visited:
                continue
            visited |= {((r1, c1), (r2, c2))}
            # vertical
            if c1 + 1 < n and grid[r1][c1+1] == 0 and c2 + 1 < n and grid[r2][c2+1] == 0:
                queue.append(((r1, c1 + 1), (r2, c2 + 1), steps+1))
            # horizontal
            if r1 + 1 < n and grid[r1+1][c1] == 0 and r2 + 1 < n and grid[r2+1][c2] == 0:
                queue.append(((r1 + 1, c1), (r2 + 1, c2), steps+1))
            # vertical
            if r1 == r2 and r1 + 1 < n and grid[r1+1][c1] + grid[r1+1][c1+1] == 0 :
                queue.append(((r1, c1), (r1 + 1, c1), steps+1))
            if c1 == c2 and c1 + 1 < n and grid[r1][c1+1] + grid[r1+1][c1+1] == 0:
                queue.append(((r1, c1), (r1, c1 + 1), steps+1))
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[[float('inf'), float('inf')] for _ in range(n + 1)] for _ in range(n + 1)]
        dp[0][1][0] = dp[1][0][0] = -1
        for r in range(1, n + 1):
            for c in range(1, n + 1):
                h, v = False, False
                if grid[r - 1][c - 1] == 0 and c < n and grid[r - 1][c] == 0:
                    dp[r][c][0] = min(dp[r - 1][c][0], dp[r][c - 1][0]) + 1
                    h = True
                if grid[r - 1][c - 1] == 0 and r < n and grid[r][c - 1] == 0:
                    dp[r][c][1] = min(dp[r - 1][c][1], dp[r][c - 1][1]) + 1
                    v = True
                if v and c < n and grid[r][c] == 0:
                    dp[r][c][1] = min(dp[r][c][1], dp[r][c][0] + 1)
                if h and r < n and grid[r][c] == 0:
                    dp[r][c][0] = min(dp[r][c][0], dp[r][c][1] + 1)
        return dp[n][n - 1][0] if dp[n][n - 1][0] < float('inf') else -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        Inf = float('inf')
        dp = [[(Inf, Inf)] * cols for _ in range(rows)]
        dp[-1][-2] = (0, Inf)
        out = lambda r, c: not (0 <= r < rows and 0 <= c < cols)
        get = lambda r, c: (Inf, Inf) if out(r, c) else dp[r][c]
        canBeHorizontal = lambda r, c: c < cols - 1 and grid[r][c+1] != 1
        canBeVertical = lambda r, c: r < rows - 1 and grid[r+1][c] != 1
        canTransform = lambda r, c: canBeVertical(r, c) and canBeHorizontal(r, c)\\
            and (r < rows - 1 and c < cols - 1 and grid[r+1][c+1] != 1)
        
        HORIZONTAL = 0
        VERTICAL = 1

        for r in range(rows - 1, -1, -1):
            for c in range(cols - 1, -1, -1):
                if grid[r][c] or (r == rows - 1 and c == cols - 2): continue
                hmove = vmove = Inf
                moveDown = get(r + 1, c)
                moveRight = get(r, c + 1)
                if canBeHorizontal(r, c):
                    hmove = 1 + min(moveDown[HORIZONTAL], moveRight[HORIZONTAL])
                if canBeVertical(r, c):
                    vmove = 1 + min(moveDown[VERTICAL], moveRight[VERTICAL])
                if canTransform(r, c):
                    hmove, vmove = min(hmove, 1 + vmove), min(vmove, 1 + hmove)
                dp[r][c] = (hmove, vmove)
        minSteps = dp[0][0][HORIZONTAL]
        if minSteps == Inf: return -1
        return minSteps
        

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        queue, visited, n = collections.deque([( (0, 0), (0, 1), 0)]), set(), len(grid)
        target = ((n-1, n-2), (n-1, n-1))
        while queue:
            (r1, c1), (r2, c2), steps = queue.popleft()
            if ((r1, c1), (r2, c2))==target:
                return steps
            if ((r1, c1), (r2, c2)) in visited:
                continue
            visited |= {((r1, c1), (r2, c2))}
            if c1 + 1 < n and grid[r1][c1+1] == 0 and c2 + 1 < n and grid[r2][c2+1] == 0:
                queue.append(((r1, c1 + 1), (r2, c2 + 1), steps+1))
            if r1 + 1 < n and grid[r1+1][c1] == 0 and r2 + 1 < n and grid[r2+1][c2] == 0:
                queue.append(((r1 + 1, c1), (r2 + 1, c2), steps+1))
            if r1 == r2 and c2 == c1 + 1 and r1 + 1 < n and grid[r1+1][c1] + grid[r1+1][c1+1] == 0 :
                queue.append(((r1, c1), (r1 + 1, c1), steps+1))
            if c1 == c2 and r2 == r1 + 1 and c1 + 1 < n and grid[r1][c1+1] + grid[r1+1][c1+1] == 0:
                queue.append(((r1, c1), (r1, c1 + 1), steps+1))
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q, seen, target = [(0, 0, 0, 0)], set(), (n - 1, n - 2, 0)              # row, column, row difference.
        for r, c, dr, steps in q:
            if (r, c, dr) == target: return steps                               # reach target.
            if (r, c, dr) not in seen:                                          # prune duplicates.
                seen.add((r, c, dr))
                if dr:                                                          # vertical position. 
                    if c + 1 < n and grid[r][c + 1] + grid[r + 1][c + 1] == 0:  # the two cells right are emtpty.
                        q += [(r, c + 1, 1, steps + 1), (r, c, 0, steps + 1)]   # right and counter-colock-wise rotate.
                    if r + 2 < n and grid[r + 2][c] == 0:                       # the below cell is empty.
                        q += [(r + 1, c, 1, steps + 1)]                         # down.
                else:                                                           # horizontal position
                    if r + 1 < n and grid[r + 1][c] + grid[r + 1][c + 1] == 0:  # the two cells below are empty.
                        q += [(r + 1, c, 0, steps + 1), (r, c, 1, steps + 1)]   # down and colock-wise rotate.
                    if c + 2 < n and grid[r][c + 2] == 0:                       # right cell is empty.
                        q += [(r, c + 1, 0, steps + 1)]                         # right.
        return -1
    
        
                


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        vis = set()
        q = collections.deque([(0, 0, 0, 0)])
        d = [[0, 1], [1, 0]]
        n = len(grid)
        while q:
            # print(q)
            node = q.popleft()
            if node[0] == (n - 1) and node[1] == (n - 2) and node[2] == 0:
                return node[3]
            snake = [[node[0], node[1]], [node[0] + d[node[2]][0], node[1] + d[node[2]][1]]]
            for i in d:
                possible = True
                for c in snake:
                    nx = c[0] + i[0]
                    ny = c[1] + i[1]
                    if nx < 0 or ny < 0 or nx >= n or ny >= n:
                        possible = False
                        break
                    if grid[nx][ny] != 0:
                        possible = False
                        break
                if possible:
                    nx = node[0] + i[0]
                    ny = node[1] + i[1]
                    if (nx, ny, node[2]) not in vis:
                        vis.add((nx, ny, node[2]))
                        q.append((nx, ny, node[2], node[3] + 1))
                    if node[2] == 0 and i[0] == 1:
                        if (node[0], node[1], 1) not in vis:
                            vis.add((node[0], node[1], 1))
                            q.append((node[0], node[1], 1, node[3] + 1))
                    elif node[2] == 1 and i[0] == 0:
                        if (node[0], node[1], 0) not in vis:
                            vis.add((node[0], node[1], 0))
                            q.append((node[0], node[1], 0, node[3] + 1))
        return -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q=[(0,0,0,1)]
        moves = 0
        visited = set([(0,0,0,1)])
        while q:
            size=len(q)
            for _ in range(size):
                x1,y1,x2,y2=q.pop(0)
                if x1==n-1 and y1==n-2 and x2==n-1 and y2==n-1:
                    return moves
#每一次蛇可以向右移动，向下移动，
#原地转圈水平变竖直与竖直变水平尾巴不动头变
                if y1+1<n and grid[x1][y1+1]==0 and y2+1<n and grid[x2][y2+1] == 0:  #向右移动
                    if (x1,y1+1,x2,y2+1) not in visited:
                        visited.add((x1,y1+1,x2,y2+1))
                        q.append((x1,y1+1,x2,y2+1))
                if x1+1<n and grid[x1+1][y1]==0 and x2+1<n and grid[x2+1][y2]==0:   #向下移动
                    if ((x1+1,y1,x2+1,y2)) not in visited:
                        visited.add((x1+1,y1,x2+1,y2))
                        q.append((x1+1,y1,x2+1,y2))
                if x1==x2 and y2==y1+1 and x1+1<n and grid[x1+1][y1]+grid[x1+1][y1+1]==0:
                    if (x1,y1,x1+1,y1) not in visited:
                        visited.add((x1,y1,x1+1,y1))
                        q.append((x1,y1,x1+1,y1))
                if y1==y2 and x2==x1+1 and y1+1<n and grid[x1][y1+1]+grid[x1+1][y1+1] == 0:  #竖直变水平
                    if (x1,y1,x1,y1+1) not in visited:
                        visited.add((x1,y1,x1,y1+1))
                        q.append((x1,y1,x1,y1+1))
            
            moves += 1
        return -1

import heapq
from typing import List


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

    self.grid = grid
    self.R, self.C = len(grid), len(grid[0])
    target = (self.R - 1, self.C - 1)

    q = [(0, 0, 1, 0)]  # (distance traveled, row, column, orientation)
    visited = [{(0, 1): 0}, {}]  # visited in horizontal state, visited in vertical state

    while q:

      d, r, c, o = heapq.heappop(q)

      # Check if snake can shift down, shift right, or rotate
      shift_d, shift_r, rot = self.shift_down(r, c, o), self.shift_right(r, c, o), self.rotate(r, c, o)

      # increment distance traveled by 1
      d += 1

      # Update the queue and visited after the snake has shifted down, right, or rotated
      if shift_d:
        i, j = shift_d
        if d < visited[o].get((i, j), float('inf')):
          visited[o][(i, j)] = d
          heapq.heappush(q, (d, i, j, o))

      if shift_r:
        i, j = shift_r
        if d < visited[o].get((i, j), float('inf')):
          visited[o][(i, j)] = d
          heapq.heappush(q, (d, i, j, o))

      if rot:
        i, j = rot
        if d < visited[1 - o].get((i, j), float('inf')):
          visited[1 - o][(i, j)] = d
          heapq.heappush(q, (d, i, j, 1 - o))

    return visited[0].get(target, -1)

  def shift_right(self, r, c, orient):
    '''returns False if snake cannot move to the right, otherwise returns new head position'''
    if (orient == 0) and ((c == self.C - 1) or self.grid[r][c + 1]): return False
    if (orient == 1) and ((c == self.C - 1) or self.grid[r][c + 1] or self.grid[r - 1][c + 1]): return False
    return (r, c + 1)

  def shift_down(self, r, c, orient):
    '''returns False if snake cannot move downwards, otherwise returns new head position'''
    if (orient == 1) and ((r == self.R - 1) or self.grid[r + 1][c]): return False
    if (orient == 0) and ((r == self.R - 1) or self.grid[r + 1][c] or self.grid[r + 1][c - 1]): return False
    return (r + 1, c)

  def rotate(self, r, c, orient):
    '''returns False if the snake is blocked from rotating, otherwise returns new head position (r,c)'''
    # horizontal to vertical CW rotation
    if (orient == 0) and ((r == self.R - 1) or self.grid[r + 1][c] or self.grid[r + 1][c - 1]): return False
    if (orient == 0): return (r + 1, c - 1)

    # vertical to horizontal CCW rotation
    if (c == self.C - 1) or self.grid[r][c + 1] or self.grid[r - 1][c + 1]: return False
    return (r - 1, c + 1)


class Solution:
    def minimumMoves(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        n = len(grid)
        if grid[-1][-1] == 1:
            return -1
        dp = [[[float('inf'), float('inf')] for i in range(n)] for j in range(n)]
        dp[0][0][0] = 0
        for j in range(1, n - 1):
            if grid[0][j + 1] == 0:
                dp[0][j][0] = dp[0][j - 1][0] + 1
            else:
                break
        for i in range(n):
            for j in range(n):
                if j < n - 1 and grid[i][j + 1] == 0 and grid[i][j] == 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][0] + 1)
                    dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0] + 1)
                if i < n - 1 and grid[i + 1][j] == 0 and grid[i][j] == 0:
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1)
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + 1)
                if i < n - 1 and j < n - 1 and grid[i][j + 1] == grid[i + 1][j] == grid[i + 1][j + 1] == 0:
                    dp[i][j][0], dp[i][j][1] = min(dp[i][j][0], dp[i][j][1] + 1), min(dp[i][j][1], dp[i][j][0] + 1)
        return dp[n - 1][n - 2][0] if dp[n - 1][n - 2][0] < float('inf') else -1


# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         n = len(grid)
#         num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
#         num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]

#         if not (grid[0][0] == grid[0][1] == 0):
#             raise ValueError

#         # initialization
#         num_steps_horizontal[0][0] = 0
#         for col in range(1, n - 1):
#             if grid[0][col] == 0:
#                 num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
#             else:
#                 break

#         if grid[1][0] == grid[1][1] == 0:
#             num_steps_vertical[0][0] = 1
#             for row in range(1, n):
#                 if grid[row][0] == 0:
#                     num_steps_vertical[row][0] = 1 + num_steps_vertical[row - 1][0]
#                 else:
#                     break

#         # iterate over num_steps_horizontal and num_steps_vertical
#         for row in range(1, n):
#             for col in range(1, n):
#                 if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
#                     num_steps_horizontal[row][col] = 1 + min(
#                         num_steps_horizontal[row][col - 1], # from left 
#                         num_steps_horizontal[row - 1][col], # from above
#                         )
#                 if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
#                     num_steps_vertical[row][col] = 1 + min(
#                         num_steps_vertical[row][col - 1], # from left 
#                         num_steps_vertical[row - 1][col], # from above
#                         )
#                 if (col < n - 1 and row < n - 1
#                    and grid[row][col] == grid[row][col + 1] == 0
#                    and grid[row][col] == grid[row + 1][col] == 0):
#                     num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
#                     num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
                    
#         if num_steps_horizontal[-1][-2] < float('inf'):
#             return num_steps_horizontal[-1][-2]
#         else:
#             return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        rows,cols = len(grid),len(grid[0])
        def getOr(x1,y1,x2,y2): return 'H' if y2 == y1 + 1 else 'V'
        def inB(x,y): return x < rows and x >= 0 and y < cols and y >= 0 
        dic = {(rows-1,cols - 2,rows-1,cols-1):0}
        def dfs(x1,y1,x2,y2,visited):
            mn = float('inf')
            visited.add((x1,y1,x2,y2))
            if (x1 == rows-1 and y1 == cols - 2 and x2 == rows-1 and y2 == cols-1): return 0
            x,y = x1,y1
            if getOr(x1,y1,x2,y2) == 'H': 
                r1,c1,r2,c2 =x,y+1,x,y+2
                if(r1,c1,r2,c2) in dic: mn = min(mn, 1 + dic[(r1,c1,r2,c2)])
                elif inB(r1,c1) and inB(r2,c2) and grid[r2][c2]==0 and (r1,c1,r2,c2) not in visited:
                    mn = min(mn, 1 + dfs(r1,c1,r2,c2,visited))
                r1,c1,r2,c2 =x+1,y,x+1,y+1
                if(r1,c1,r2,c2) in dic: mn = min(mn, 1 + dic[(r1,c1,r2,c2)])
                elif inB(r1,c1) and inB(r2,c2) and grid[r1][c1]==0 and grid[r2][c2]==0 and (r1,c1,r2,c2) not in visited:
                    mn = min(mn, 1 + dfs(r1,c1,r2,c2,visited))
                r1,c1,r2,c2 = x,y,x+1,y
                if(r1,c1,r2,c2) in dic: mn = min(mn, 1 + dic[(r1,c1,r2,c2)])
                elif inB(r1,c1) and inB(r2,c2) and grid[r2][c2]==0 and grid[r2][c2+1]==0  and (r1,c1,r2,c2) not in visited:
                    mn = min(mn, 1 + dfs(r1,c1,r2,c2,visited))
            else:
                r1,c1,r2,c2 = x+1,y,x+2,y
                if(r1,c1,r2,c2) in dic: mn = min(mn, 1 + dic[(r1,c1,r2,c2)])
                elif inB(r1,c1) and inB(r2,c2) and grid[r2][c2]==0 and (r1,c1,r2,c2) not in visited:
                    mn = min(mn, 1 + dfs(r1,c1,r2,c2,visited))
                r1,c1,r2,c2 = x,y+1,x+1,y+1
                if(r1,c1,r2,c2) in dic: mn = min(mn, 1 + dic[(r1,c1,r2,c2)])
                elif inB(r1,c1) and inB(r2,c2) and grid[r1][c1]==0 and grid[r2][c2]==0 and (r1,c1,r2,c2) not in visited:
                    mn = min(mn, 1 + dfs(r1,c1,r2,c2,visited))
                r1,c1,r2,c2 = x,y,x,y+1
                if(r1,c1,r2,c2) in dic: mn = min(mn, 1 + dic[(r1,c1,r2,c2)])
                elif inB(r1,c1) and inB(r2,c2) and grid[r2+1][c2]==0 and grid[r2][c2]==0 and (r1,c1,r2,c2) not in visited:
                    mn = min(mn, 1 + dfs(r1,c1,r2,c2,visited))
            dic[(x1,y1,x2,y2)] = mn
            return mn
                                          
        
        d =  dfs(0,0,0,1,set())
        return d if d != float('inf') else -1
                
                    
                


class Solution:
    def minimumMoves(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        n = len(grid)
        if grid[-1][-1] == 1:
            return -1
        dp = [[[float('inf'), float('inf')] for i in range(n)] for j in range(n)]
        dp[0][0][0] = 0
        for j in range(1, n - 1):
            if grid[0][j + 1] == 0:
                dp[0][j][0] = dp[0][j - 1][0] + 1
            else:
                break
        for i in range(n):
            for j in range(n):
                if j < n - 1 and grid[i][j + 1] == 0 and grid[i][j] == 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][0] + 1)
                    dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0] + 1)
                if i < n - 1 and grid[i + 1][j] == 0 and grid[i][j] == 0:
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1)
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + 1)
                if i < n - 1 and j < n - 1 and grid[i][j] == 0 and grid[i][j + 1] == grid[i + 1][j] == grid[i + 1][j + 1] == 0:
                    dp[i][j][0], dp[i][j][1] = min(dp[i][j][0], dp[i][j][1] + 1), min(dp[i][j][1], dp[i][j][0] + 1)
        return dp[n - 1][n - 2][0] if dp[n - 1][n - 2][0] < float('inf') else -1


# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         n = len(grid)
#         num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
#         num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]

#         if not (grid[0][0] == grid[0][1] == 0):
#             raise ValueError

#         # initialization
#         num_steps_horizontal[0][0] = 0
#         for col in range(1, n - 1):
#             if grid[0][col] == 0:
#                 num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
#             else:
#                 break

#         if grid[1][0] == grid[1][1] == 0:
#             num_steps_vertical[0][0] = 1
#             for row in range(1, n):
#                 if grid[row][0] == 0:
#                     num_steps_vertical[row][0] = 1 + num_steps_vertical[row - 1][0]
#                 else:
#                     break

#         # iterate over num_steps_horizontal and num_steps_vertical
#         for row in range(1, n):
#             for col in range(1, n):
#                 if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
#                     num_steps_horizontal[row][col] = 1 + min(
#                         num_steps_horizontal[row][col - 1], # from left 
#                         num_steps_horizontal[row - 1][col], # from above
#                         )
#                 if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
#                     num_steps_vertical[row][col] = 1 + min(
#                         num_steps_vertical[row][col - 1], # from left 
#                         num_steps_vertical[row - 1][col], # from above
#                         )
#                 if (col < n - 1 and row < n - 1
#                    and grid[row][col] == grid[row][col + 1] == 0
#                    and grid[row + 1][col] == grid[row + 1][col + 1] == 0):
#                     num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
#                     num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
                    
#         # print(num_steps_horizontal)
#         print(num_steps_vertical)
        
#         if num_steps_horizontal[-1][-2] < float('inf'):
#             return num_steps_horizontal[-1][-2]
#         else:
#             return -1

class Solution:
    def minimumMoves(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        n = len(grid)
        if grid[-1][-1] == 1:
            return -1
        dp = [[[float('inf'), float('inf')] for i in range(n)] for j in range(n)]
        dp[0][0][0] = 0
        for j in range(1, n - 1):
            if grid[0][j + 1] == 0:
                dp[0][j][0] = dp[0][j - 1][0] + 1
            else:
                break
        
        if grid[1][0] == grid[1][1] == 0:
            for i in range(1, n - 1):
                if grid[i][0] == 0:
                    dp[i][0][1] = dp[i - 1][0][1] + 1
                else:
                    break

        
        for i in range(n):
            for j in range(n):
                if j < n - 1 and grid[i][j + 1] == 0 and grid[i][j] == 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][0] + 1)
                    dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0] + 1)
                if i < n - 1 and grid[i + 1][j] == 0 and grid[i][j] == 0:
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1)
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + 1)
                if i < n - 1 and j < n - 1 and grid[i][j] == 0 and grid[i][j + 1] == grid[i + 1][j] == grid[i + 1][j + 1] == 0:
                    dp[i][j][0], dp[i][j][1] = min(dp[i][j][0], dp[i][j][1] + 1), min(dp[i][j][1], dp[i][j][0] + 1)
        return dp[n - 1][n - 2][0] if dp[n - 1][n - 2][0] < float('inf') else -1


# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         n = len(grid)
#         num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
#         num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]

#         if not (grid[0][0] == grid[0][1] == 0):
#             raise ValueError

#         # initialization
#         num_steps_horizontal[0][0] = 0
#         for col in range(1, n - 1):
#             if grid[0][col] == 0:
#                 num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
#             else:
#                 break

#         if grid[1][0] == grid[1][1] == 0:
#             num_steps_vertical[0][0] = 1
#             for row in range(1, n):
#                 if grid[row][0] == 0:
#                     num_steps_vertical[row][0] = 1 + num_steps_vertical[row - 1][0]
#                 else:
#                     break

#         # iterate over num_steps_horizontal and num_steps_vertical
#         for row in range(1, n):
#             for col in range(1, n):
#                 if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
#                     num_steps_horizontal[row][col] = 1 + min(
#                         num_steps_horizontal[row][col - 1], # from left 
#                         num_steps_horizontal[row - 1][col], # from above
#                         )
#                 if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
#                     num_steps_vertical[row][col] = 1 + min(
#                         num_steps_vertical[row][col - 1], # from left 
#                         num_steps_vertical[row - 1][col], # from above
#                         )
#                 if (col < n - 1 and row < n - 1
#                    and grid[row][col] == grid[row][col + 1] == 0
#                    and grid[row + 1][col] == grid[row + 1][col + 1] == 0):
#                     num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
#                     num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
                    
#         # print(num_steps_horizontal)
#         print(num_steps_vertical)
        
#         if num_steps_horizontal[-1][-2] < float('inf'):
#             return num_steps_horizontal[-1][-2]
#         else:
#             return -1

class Solution:
    def minimumMoves(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        n = len(grid)
        if grid[-1][-1] == 1:
            return -1
        dp = [[[float('inf'), float('inf')] for i in range(n)] for j in range(n)]
        dp[0][0][0] = 0
        for j in range(1, n - 1):
            if grid[0][j + 1] == 0:
                dp[0][j][0] = dp[0][j - 1][0] + 1
            else:
                break
        
        if grid[1][0] == grid[1][1] == 0:
            for i in range(1, n - 1):
                if grid[i + 1][0] == 0:
                    dp[i][0][1] = dp[i - 1][0][1] + 1
                else:
                    break

        
        for i in range(n):
            for j in range(n):
                if j < n - 1 and grid[i][j + 1] == 0 and grid[i][j] == 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][0] + 1)
                    dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0] + 1)
                if i < n - 1 and grid[i + 1][j] == 0 and grid[i][j] == 0:
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1)
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + 1)
                if i < n - 1 and j < n - 1 and grid[i][j] == 0 and grid[i][j + 1] == grid[i + 1][j] == grid[i + 1][j + 1] == 0:
                    dp[i][j][0], dp[i][j][1] = min(dp[i][j][0], dp[i][j][1] + 1), min(dp[i][j][1], dp[i][j][0] + 1)
        return dp[n - 1][n - 2][0] if dp[n - 1][n - 2][0] < float('inf') else -1


# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         n = len(grid)
#         num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
#         num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]

#         if not (grid[0][0] == grid[0][1] == 0):
#             raise ValueError

#         # initialization
#         num_steps_horizontal[0][0] = 0
#         for col in range(1, n - 1):
#             if grid[0][col] == 0:
#                 num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
#             else:
#                 break

#         if grid[1][0] == grid[1][1] == 0:
#             num_steps_vertical[0][0] = 1
#             for row in range(1, n):
#                 if grid[row][0] == 0:
#                     num_steps_vertical[row][0] = 1 + num_steps_vertical[row - 1][0]
#                 else:
#                     break

#         # iterate over num_steps_horizontal and num_steps_vertical
#         for row in range(1, n):
#             for col in range(1, n):
#                 if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
#                     num_steps_horizontal[row][col] = 1 + min(
#                         num_steps_horizontal[row][col - 1], # from left 
#                         num_steps_horizontal[row - 1][col], # from above
#                         )
#                 if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
#                     num_steps_vertical[row][col] = 1 + min(
#                         num_steps_vertical[row][col - 1], # from left 
#                         num_steps_vertical[row - 1][col], # from above
#                         )
#                 if (col < n - 1 and row < n - 1
#                    and grid[row][col] == grid[row][col + 1] == 0
#                    and grid[row + 1][col] == grid[row + 1][col + 1] == 0):
#                     num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
#                     num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
                    
#         # print(num_steps_horizontal)
#         print(num_steps_vertical)
        
#         if num_steps_horizontal[-1][-2] < float('inf'):
#             return num_steps_horizontal[-1][-2]
#         else:
#             return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        '''
        BFS
        Time: O(n^2)
        Space: O(n)
        '''
        n = len(grid)
        start = (0, 0, 0)
        end = (n-1, n-2, 0)
        queue = {start}
        seen = set()
        steps = 0
        while queue:
            newQueue = set()
            for i, j, d in queue:
                if (i, j, d) == end: return steps
                seen.add((i, j, d))
                if d == 0:
                    if j + 2 < n and not grid[i][j+2]:
                        if (i, j+1, 0) not in seen: newQueue.add((i, j+1, 0))
                    if i + 1 < n and not grid[i+1][j] and not grid[i+1][j+1]:
                        if (i+1, j, 0) not in seen: newQueue.add((i+1, j, 0))
                        if (i, j, 1) not in seen: newQueue.add((i, j, 1))
                else:
                    if i + 2 < n and not grid[i+2][j]:
                        if (i+1, j, 1) not in seen: newQueue.add((i+1, j, 1))
                    if j + 1 < n and not grid[i][j+1] and not grid[i+1][j+1]:
                        if (i, j+1, 1) not in seen: newQueue.add((i, j+1, 1))
                        if (i, j, 0) not in seen: newQueue.add((i, j, 0))

            queue = newQueue
            steps += 1
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if not grid[n - 1][n - 2] == grid[n - 1][n - 1] == 0:
            return -1
        
        locs = set([(0, 0, 'h'), ]) #(i, j, alignment, just rotated)
        visited = set(locs)
        time = 0
        while locs and (n-1, n-2, 'h') not in locs and (n-1, n-2, 'h') not in locs:
            time += 1
            new_locs = set()
            for i, j, align in locs:
                # move right
                if align == 'h' and j + 2 < n and (i, j+1, 'h') not in visited and not grid[i][j+2]:
                    new_locs.add((i, j + 1, 'h'))
                if align == 'v' and j + 1 < n and (i, j+1, 'v') not in visited and not grid[i][j+1] and not grid[i+1][j+1]:
                    new_locs.add((i, j + 1, 'v'))
                # move down
                if align == 'h' and i + 1 < n and (i+1, j, 'h') not in visited and not grid[i+1][j] and not grid[i+1][j+1]:
                    new_locs.add((i+1, j, 'h'))
                if align == 'v' and i + 2 < n and (i+1, j, 'v') not in visited and not grid[i+2][j]:
                    new_locs.add((i+1, j, 'v'))
                # hor -> vert
                if align == 'h' and i + 1 < n and (i, j, 'v') not in visited and not grid[i+1][j] and not grid[i+1][j+1]:
                    new_locs.add((i, j, 'v'))
                # vert -> hor
                if align == 'v' and j + 1 < n and (i, j, 'h') not in visited and not grid[i][j+1] and not grid[i+1][j+1]:
                    new_locs.add((i, j, 'h'))
            locs = set(new_locs)
            visited |= locs
            
        if (n-1, n-2, 'h') in locs or (n-1, n-2, 'h') in locs:
            return time
        
        else:
            return -1


class Solution:
    def minimumMoves(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        n = len(grid)
        if grid[-1][-1] == 1:
            return -1
        dp = [[[float('inf'), float('inf')] for i in range(n)] for j in range(n)]
        dp[0][0][0] = 0
        for j in range(1, n - 1):
            if grid[0][j + 1] == 0:
                dp[0][j][0] = dp[0][j - 1][0] + 1
            else:
                break
        for i in range(n):
            for j in range(n):
                if j < n - 1 and grid[i][j + 1] == 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][0] + 1)
                    if grid[i][j] == 0:
                        dp[i][j][0] = min(dp[i][j][0],dp[i - 1][j][0] + 1)
                if i < n - 1 and grid[i + 1][j] == 0:
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1)
                    if grid[i][j] == 0:
                        dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + 1)
                if i < n - 1 and j < n - 1 and grid[i][j + 1] == grid[i + 1][j] == grid[i + 1][j + 1] == 0:
                    dp[i][j][0], dp[i][j][1] = min(dp[i][j][0], dp[i][j][1] + 1), min(dp[i][j][1], dp[i][j][0] + 1)
        return dp[n - 1][n - 2][0] if dp[n - 1][n - 2][0] < float('inf') else -1


# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         n = len(grid)
#         num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
#         num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]

#         if not (grid[0][0] == grid[0][1] == 0):
#             raise ValueError

#         # initialization
#         num_steps_horizontal[0][0] = 0
#         for col in range(1, n - 1):
#             if grid[0][col] == 0:
#                 num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
#             else:
#                 break

#         if grid[1][0] == grid[1][1] == 0:
#             num_steps_vertical[0][0] = 1
#             for row in range(1, n):
#                 if grid[row][0] == 0:
#                     num_steps_vertical[row][0] = 1 + num_steps_vertical[row - 1][0]
#                 else:
#                     break

#         # iterate over num_steps_horizontal and num_steps_vertical
#         for row in range(1, n):
#             for col in range(1, n):
#                 if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
#                     num_steps_horizontal[row][col] = 1 + min(
#                         num_steps_horizontal[row][col - 1], # from left 
#                         num_steps_horizontal[row - 1][col], # from above
#                         )
#                 if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
#                     num_steps_vertical[row][col] = 1 + min(
#                         num_steps_vertical[row][col - 1], # from left 
#                         num_steps_vertical[row - 1][col], # from above
#                         )
#                 if (col < n - 1 and row < n - 1
#                    and grid[row][col] == grid[row][col + 1] == 0
#                    and grid[row][col] == grid[row + 1][col] == 0):
#                     num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
#                     num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
                    
#         if num_steps_horizontal[-1][-2] < float('inf'):
#             return num_steps_horizontal[-1][-2]
#         else:
#             return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        # BFS
        orientation = 'h' # horizontal
        head, tail = (0, 1), (0, 0)
        q = collections.deque()
        q.append((head, tail, orientation))
        visited = set()
        visited.add((head, tail, orientation))
        moves = 0
        n = len(grid)
        target_head, target_tail = (n-1, n-1), (n-1, n-2)
        
        while q:
            for _ in range(len(q)):
                head, tail, orientation = q.popleft()
                if head == target_head and tail == target_tail:
                    return moves
                head_x, head_y = head
                tail_x, tail_y = tail
                if orientation == 'h':
                    # move right
                    if head_y + 1 < n and grid[head_x][head_y + 1] == 0:
                        node = ((head_x, head_y + 1), head, orientation)
                        if node not in visited:
                            q.append(node)
                            visited.add(node)
                    # move down
                    if head_x + 1 < n and grid[head_x + 1][head_y] == 0 and grid[tail_x + 1][tail_y] == 0:
                        node = ((head_x + 1, head_y), (tail_x + 1, tail_y), orientation)
                        if node not in visited:
                            q.append(node)
                            visited.add(node)
                    # rotate clockwise
                    if head_x + 1 < n and grid[head_x + 1][head_y] == 0 and grid[head_x + 1][tail_y] == 0:
                        node = ((tail_x + 1, tail_y), tail, 'v')
                        if node not in visited:
                            q.append(node)
                            visited.add(node)
                        
                else:
                    # move right
                    if head_y + 1 < n and grid[head_x][head_y + 1] == 0 and grid[tail_x][tail_y + 1] == 0:
                        node = ((head_x, head_y + 1), (tail_x, tail_y + 1), 'v')
                        if node not in visited:
                            q.append(node)
                            visited.add(node)
                    # move down
                    if head_x + 1 < n and grid[head_x + 1][head_y] == 0:
                        node = ((head_x + 1, head_y), head, 'v')
                        if node not in visited:
                            q.append(node)
                            visited.add(node)
                    # rotate counter-clockwise
                    if head_y + 1 < n and grid[head_x][head_y + 1] == 0 and grid[tail_x][tail_y + 1] == 0:
                        node = ((tail_x, tail_y + 1), tail, 'h')
                        if node not in visited:
                            q.append(node)
                            visited.add(node)
            moves += 1
            
        return -1


class Solution:
    def bfs(self, M: List[List[List[int]]]) -> int:
        Q = deque()
        visited = set()
        Q.append((0, 0, 0, 0))
        visited.add((0, 0, 0))
        while(len(Q) != 0):
            k, i, j, depth = Q.popleft()
            if(depth > 25):
                print(k, i, j, depth)
            if((k, i, j) == (0, self.m-1, self.n-2)):
                return depth
            if(j+1 < len(M[k][i]) and (k, i, j+1) not in visited and M[k][i][j+1] == 0):
                Q.append((k, i, j+1, depth + 1))
                visited.add((k, i, j+1))
            if(i+1 < len(M[k]) and (k, i+1, j) not in visited and M[k][i+1][j] == 0):
                Q.append((k, i+1, j, depth + 1))
                visited.add((k, i+1, j))
            if(i+1 < self.n and j+1 < self.m and (k^1, i, j) not in visited and M[2][i][j] == 0):
                Q.append((k^1, i, j, depth + 1))
                visited.add((k^1, i, j))
        return -1
    
    def minimumMoves(self, grid: List[List[int]]) -> int:
        self.m = len(grid)
        self.n = len(grid[0])
        M = [[[0] * (self.n-1) for i in range(self.m)], [[0] * (self.n) for i in range(self.m - 1)], [[0] * (self.n - 1) for i in range(self.m - 1)]]
        for i in range(self.m):
            for j in range(self.n):
                if(j+1 < self.n):
                    M[0][i][j] = (grid[i][j] | grid[i][j+1])
                if(i+1 < self.m):
                    M[1][i][j] = (grid[i][j] | grid[i+1][j])
                if(i+1 < self.m and j+1 < self.n):
                    M[2][i][j] = (grid[i][j] | grid[i+1][j] | grid[i][j+1] | grid[i+1][j+1])
        return self.bfs(M)

from collections import deque

class Solution:    
    dx = [1, 0]
    dy = [0, 1]
    def minimumMoves(self, grid: List[List[int]]) -> int:
        visit = set()
        q = deque()
        n = len(grid)
        answer = float('inf')
        #x1, y1, x2, y2, is_horizon, time
        #   is_horozon = 1 : 가로
        #   is_horizon = 0 : 세로
        init_pos = [0, 0, 0, 1, 1, 0]
        q.append(init_pos)
        
        while q:
            x1, y1, x2, y2, is_horizon, cost = q.popleft()
            if cost>=20:
                print((x1,y1,x2,y2, is_horizon, cost))
            
            if is_horizon and x1==n-1 and x2==n-1 and y2==n-1 and y1==n-2:
                answer = min(answer, cost)
            
            visit.add(((x1, y1), (x2, y2)))
            
            for i in range(2):
                nx1 = x1 + self.dx[i]
                ny1 = y1 + self.dy[i]
                nx2 = x2 + self.dx[i]
                ny2 = y2 + self.dy[i]
                
                if 0<=nx1<n and 0<=ny1<n and 0<=nx2<n and 0<=ny2<n and grid[nx1][ny1]==0 and grid[nx2][ny2]==0:
                    if ((nx1, ny1),(nx2, ny2)) not in visit:
                        nxt_hrizon = 1 if nx1==nx2 else 0
                        visit.add(((nx1, ny1),(nx2, ny2)))
                        q.append([nx1, ny1, nx2, ny2, nxt_hrizon, cost+1])
            #rotataion
            if is_horizon:
                if x1 < n-1 and grid[x1+1][y1]==0 and grid[x2+1][y2]==0:
                #clockwise
                    if ((x1, y1), (x2+1, y2-1)) not in visit:
                        visit.add(((x1, y1), (x2+1, y2-1)))
                        q.append([x1, y1, x2+1, y2-1, 0, cost+1])
                
            else:
                #counterclockwise
                if y1 < n-1 and grid[x1][y1+1]==0 and grid[x2][y2+1]==0:
                    if ((x1, y1), (x2-1, y2+1)) not in visit:
                        visit.add(((x1, y1), (x2-1, y2+1)))
                        q.append([x1, y1, x2-1, y2+1, 1, cost+1])
        # print(answer)
        if answer!=float('inf'):
            return answer
        else:
            return -1
                    


from collections import deque

class Solution:    
    dx = [1, 0]
    dy = [0, 1]
    def minimumMoves(self, grid: List[List[int]]) -> int:
        visit = set()
        q = deque()
        n = len(grid)
        answer = float('inf')
        #x1, y1, x2, y2, is_horizon, time
        #   is_horozon = 1 : 가로
        #   is_horizon = 0 : 세로
        init_pos = [0, 0, 0, 1, 1, 0]
        q.append(init_pos)
        
        while q:
            x1, y1, x2, y2, is_horizon, cost = q.popleft()
            if cost>=20:
                print((x1,y1,x2,y2, is_horizon, cost))
            
            if is_horizon and x1==n-1 and x2==n-1 and y2==n-1 and y1==n-2:
                answer = min(answer, cost)
            
            visit.add(((x1, y1), (x2, y2)))
            
            for i in range(2):
                nx1 = x1 + self.dx[i]
                ny1 = y1 + self.dy[i]
                nx2 = x2 + self.dx[i]
                ny2 = y2 + self.dy[i]
                
                if 0<=nx1<n and 0<=ny1<n and 0<=nx2<n and 0<=ny2<n and grid[nx1][ny1]==0 and grid[nx2][ny2]==0:
                    if ((nx1, ny1),(nx2, ny2)) not in visit:
                        nxt_hrizon = 1 if nx1==nx2 else 0
                        visit.add(((nx1, ny1),(nx2, ny2)))
                        q.append([nx1, ny1, nx2, ny2, nxt_hrizon, cost+1])
            #rotataion
            if is_horizon:
                if x1 < n-1 and grid[x1+1][y1]==0 and grid[x2+1][y2]==0:
                #clockwise
                    if ((x1, y1), (x2+1, y2-1)) not in visit:
                        visit.add(((x1, y1), (x2+1, y2-1)))
                        q.append([x1, y1, x2+1, y2-1, 0, cost+1])
                
            else:
                #counterclockwise
                if y1 < n-1 and grid[x1][y1+1]==0 and grid[x2][y2+1]==0:
                    if ((x1, y1), (x2-1, y2+1)) not in visit:
                        visit.add(((x1, y1), (x2-1, y2+1)))
                        q.append([x1, y1, x2-1, y2+1, 1, cost+1])
                        
        return answer if answer!=float('inf') else -1


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        m = n = len(grid)
        visited = {(1, 0)}
        q = collections.deque([(1, 0)])
        moves = 0
        while q:
            for _ in range(len(q)):
                h, t = q.popleft()
                ti, tj = divmod(t, n)
                hi, hj = divmod(h, n)
                if hi == n - 1 and hj == n - 1 and ti == n - 1:
                    return moves
                for di, dj in [[0, 1], [1, 0]]:
                    hii = hi + di
                    hjj = hj + dj
                    tii = ti + di
                    tjj = tj + dj
                    if hii < n and hjj < n and tii < n and tjj < n and grid[hii][hjj] != 1 and grid[tii][tjj] != 1:
                        next = (hii * n + hjj, tii * n + tjj)
                        if hii == hjj == tii == n - 1:
                            return moves + 1
                        if next not in visited:
                            q.append(next)
                            visited.add(next)
                        if di == 1 and hi == ti:
                            next = (h + n - 1, t)
                            if next not in visited:
                                q.append(next)
                                visited.add(next)
                        if dj == 1 and hj == tj:
                            next = (h - n + 1, t)
                            if next not in visited:
                                q.append(next)
                                visited.add(next)
            moves += 1
        return -1


\"\"\"
DP bottom up time O(m*n) space O(m*n)
\"\"\"

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        \"\"\"
        snake tail originally at grid[0][0]
        mm[i][j][0] := steps to get to grid[i][j] in horizontal position
        mm[i][j][1] := steps to get to grid[i][j] in vertical position
        \"\"\"
        if len(grid) == 0: return 0  # no dungeon
        elif len(grid) == 1 and len(grid[0]) == 2: return 0

        n = len(grid)  # number of rows
        m = len(grid[0]) # number of columns
        mm = [[[math.inf, math.inf] for _ in range(m+1)] for _ in range(n+1)]
       
        for i in range(1, n+1):
            for j in range(1, m+1):
                ig = i-1
                jg = j-1
                if i==1 and j==1:
                    mm[1][1][0] = 0 # initial tail position
                else:
                    # move from up or left
                    if j<m and grid[ig][jg]==0 and grid[ig][jg+1]==0:
                        mm[i][j][0] = min(mm[i][j-1][0], mm[i-1][j][0])+1
                    # move from up or left
                    if i<n and grid[ig][jg]==0 and grid[ig+1][jg]==0:
                        mm[i][j][1] = min(mm[i][j-1][1], mm[i-1][j][1])+1
                # rotate
                if j<m and i<n and grid[ig][jg]==0 and grid[ig][jg+1]==0 and grid[ig+1][jg]==0 and grid[ig+1][jg+1]==0:
                    mm[i][j][0] = min(mm[i][j][0], mm[i][j][1]+1)
                    mm[i][j][1] = min(mm[i][j][1], mm[i][j][0]+1)
        if mm[n][m-1][0]==math.inf:
            return -1
        return mm[n][m-1][0]


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        
        n = len(grid)
        q = collections.deque()
        q.append((0,0,0,0))
        visited = set()
        
        while q:
            r, c, direction, steps = q.popleft()
            
            if (r,c,direction) == (n-1, n-2, 0):
                return steps
            if (r,c, direction) not in visited:
                visited.add((r,c, direction))
                if direction:
                    if c + 1 < n and grid[r][c + 1] + grid[r + 1][c + 1] == 0:
                        q.append((r, c + 1, 1, steps + 1))
                        q.append((r, c, 0, steps + 1))
                    if r + 2 < n and grid[r + 2][c] == 0:
                        q.append((r + 1, c, 1, steps + 1)) 
                else:
                    if r + 1 < n and grid[r + 1][c] + grid[r + 1][c + 1] == 0:
                        q.append((r + 1, c, 0, steps + 1))
                        q.append((r, c, 1, steps + 1))

                    if c + 2 < n and grid[r][c + 2] == 0: 
                        q.append((r, c + 1, 0, steps + 1))

        return -1
                    
                
                


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        '''
        最短步数，利用BFS。有四种移动方式
        向右，向下，水平竖直
        '''
        n = len(grid)
        q=[(0,0,0,1)]
        moves = 0
        visited = set([(0,0,0,1)])
        while q:
            size=len(q)
            for _ in range(size):
                x1,y1,x2,y2=q.pop(0)
                if x1==n-1 and y1==n-2 and x2==n-1 and y2==n-1:
                    return moves
                #向右移动
                if y1+1<n and grid[x1][y1+1]==0 and y2+1<n and grid[x2][y2+1] == 0:
                    if (x1,y1+1,x2,y2+1) not in visited:
                        visited.add((x1,y1+1,x2,y2+1))
                        q.append((x1,y1+1,x2,y2+1))
                #向下移动
                if x1+1<n and grid[x1+1][y1]==0 and x2+1<n and grid[x2+1][y2]==0:
                    if ((x1+1,y1,x2+1,y2)) not in visited:
                        visited.add((x1+1,y1,x2+1,y2))
                        q.append((x1+1,y1,x2+1,y2))
                #水平变竖直
                if x1==x2 and y2==y1+1 and x1+1<n and grid[x1+1][y1]+grid[x1+1][y1+1]==0:
                    if (x1,y1,x1+1,y1) not in visited:
                        visited.add((x1,y1,x1+1,y1))
                        q.append((x1,y1,x1+1,y1))
                #竖直变水平
                if y1==y2 and x2==x1+1 and y1+1<n and grid[x1][y1+1]+grid[x1+1][y1+1] == 0: 
                    if (x1,y1,x1,y1+1) not in visited:
                        visited.add((x1,y1,x1,y1+1))
                        q.append((x1,y1,x1,y1+1))
            
            moves += 1
        return -1

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        
        
        queue = deque()
        
        queue.append([0,0,0,0])
        
        visited = {(0,0,0):1}
        n = len(grid)
        
        while(len(queue) >0):
            
            x, y, dic, step = queue.popleft()
            #print(x, y, dic, step)
            if x == n-1 and y == n-2 and dic == 0:
                return step
            
            if dic == 0:
                nx, ny = x, y+1
                if nx >=0 and nx < n and ny >=0 and ny+1 < n:
                    if grid[nx][ny+1] == 0 and (nx, ny, 0) not in visited:
                        queue.append([nx, ny, 0, step + 1])
                        visited[(nx, ny, 0)] =1
            
                nx, ny = x, y
                checkx1, checky1 = x+1, y
                checkx, checky = x+1, y+1
                if checkx1 >=0 and checkx1 < n and checky1 >=0 and checky1 < n:
                    if checkx >=0 and checkx < n and checky >=0 and checky < n:
                        if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and(nx, ny, 1) not in visited:
                            queue.append([nx, ny, 1, step + 1])
                            visited[(nx, ny, 1)] =1  
 
                        if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and(checkx1, checky1, 0) not in visited:
                            queue.append([checkx1, checky1, 0, step + 1])
                            visited[(checkx1, checky1, 0)] =1  

            if dic == 1:
                nx, ny = x+1, y
                if nx >=0 and nx+1 < n and ny >=0 and ny < n:
                    if grid[nx+1][ny] == 0 and (nx, ny, 1) not in visited:
                        queue.append([nx, ny, 1, step + 1])
                        visited[(nx, ny, 1)] =1
            
                nx, ny = x, y
                checkx1, checky1 = x, y+1
                checkx, checky = x+1, y+1
                if checkx1 >=0 and checkx1 < n and checky1 >=0 and checky1 < n:
                    if checkx >=0 and checkx < n and checky >=0 and checky < n:
                        if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and(nx, ny, 0) not in visited:
                            queue.append([nx, ny, 0, step + 1])
                            visited[(nx, ny, 0)] =1
                            #print(x, y, nx, ny, checkx1, checky1, grid[checkx1][checky1], dic)
                        if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and(x, y+1, 1) not in visited:
                            queue.append([x, y+1, 1, step + 1])
                            visited[(x, y+1, 1)] =1           
        return -1