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

<p>In one move the snake can:</p>

<ul>
	<li>Move one cell to the right&nbsp;if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.</li>
	<li>Move down one cell&nbsp;if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.</li>
	<li>Rotate clockwise if it&#39;s in a horizontal position and the two cells under it are both empty. In that case the snake moves from&nbsp;<code>(r, c)</code>&nbsp;and&nbsp;<code>(r, c+1)</code>&nbsp;to&nbsp;<code>(r, c)</code>&nbsp;and&nbsp;<code>(r+1, c)</code>.<br />
	<img alt="" src="https://assets.leetcode.com/uploads/2019/09/24/image-2.png" style="width: 300px; height: 134px;" /></li>
	<li>Rotate counterclockwise&nbsp;if it&#39;s in a vertical position and the two cells to its right are both empty. In that case the snake moves from&nbsp;<code>(r, c)</code>&nbsp;and&nbsp;<code>(r+1, c)</code>&nbsp;to&nbsp;<code>(r, c)</code>&nbsp;and&nbsp;<code>(r, c+1)</code>.<br />
	<img alt="" src="https://assets.leetcode.com/uploads/2019/09/24/image-1.png" style="width: 300px; height: 121px;" /></li>
</ul>

<p>Return the minimum number of moves to reach the target.</p>

<p>If there is no way to reach the target, return&nbsp;<code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/24/image.png" style="width: 400px; height: 439px;" /></strong></p>

<pre>
<strong>Input:</strong> grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
&nbsp;              [0,0,0,0,1,1],
&nbsp;              [0,0,1,0,1,0],
&nbsp;              [0,1,1,0,0,0],
&nbsp;              [0,1,1,0,0,0]]
<strong>Output:</strong> 11
<strong>Explanation:
</strong>One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[0,0,1,1,1,1],
&nbsp;              [0,0,0,0,1,1],
&nbsp;              [1,1,0,0,0,1],
&nbsp;              [1,1,1,0,0,1],
&nbsp;              [1,1,1,0,0,1],
&nbsp;              [1,1,1,0,0,0]]
<strong>Output:</strong> 9
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 1</code></li>
	<li>It is guaranteed that the snake starts at empty cells.</li>
</ul>

from collections import deque
from typing import List, Tuple

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        
        # Directions for movement: right, down
        directions = [(0, 1), (1, 0)]
        
        # Initial state: (row, col, orientation, steps)
        # Orientation: 0 for horizontal, 1 for vertical
        queue = deque([(0, 0, 0, 0)])  # Start at (0, 0) with horizontal orientation
        visited = set((0, 0, 0))  # Keep track of visited states
        
        while queue:
            r, c, orientation, steps = queue.popleft()
            
            # Check if we've reached the target position
            if (r == n - 1 and c == n - 2 and orientation == 0):
                return steps
            
            # Try moving right or down
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if orientation == 0:  # Horizontal
                    if nr < n and nc + 1 < n and grid[nr][nc] == 0 and grid[nr][nc + 1] == 0:
                        if (nr, nc, 0) not in visited:
                            visited.add((nr, nc, 0))
                            queue.append((nr, nc, 0, steps + 1))
                else:  # Vertical
                    if nr + 1 < n and nc < n and grid[nr][nc] == 0 and grid[nr + 1][nc] == 0:
                        if (nr, nc, 1) not in visited:
                            visited.add((nr, nc, 1))
                            queue.append((nr, nc, 1, steps + 1))
            
            # Try rotating
            if orientation == 0:  # Horizontal to Vertical
                if r + 1 < n and grid[r + 1][c] == 0 and grid[r + 1][c + 1] == 0:
                    if (r, c, 1) not in visited:
                        visited.add((r, c, 1))
                        queue.append((r, c, 1, steps + 1))
            else:  # Vertical to Horizontal
                if c + 1 < n and grid[r][c + 1] == 0 and grid[r + 1][c + 1] == 0:
                    if (r, c, 0) not in visited:
                        visited.add((r, c, 0))
                        queue.append((r, c, 0, steps + 1))
        
        return -1  # If no path is found

# Example usage:
# solution = Solution()
# print(solution.minimumMoves([[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
18400