<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

class Solution:
    def __init__(self):
        self.grid_size = 0
        self.grid = []
        self.visited_states = []
        self.bfs_queue = deque()

    def minimumMoves(self, grid):
        self.grid = grid
        self.grid_size = len(grid)
        self.visited_states = [[False] * 2 for _ in range(self.grid_size * self.grid_size)]
        target_position = (self.grid_size * self.grid_size - 2, self.grid_size * self.grid_size - 1)
        self.bfs_queue.append((0, 1))  # Starting state (head at 0 and tail at 1)
        self.visited_states[0][0] = True  # Set the starting state as visited with horizontal orientation
        
        steps_count = 0
        
        while self.bfs_queue:
            level_size = len(self.bfs_queue)
            for _ in range(level_size):
                head, tail = self.bfs_queue.popleft()
                
                # If the current position is the target, return the steps count
                if (head, tail) == target_position:
                    return steps_count

                # Calculate coordinates from serialized positions
                head_row = head // self.grid_size
                head_col = head % self.grid_size
                tail_row = tail // self.grid_size
                tail_col = tail % self.grid_size

                # Try moving right and down for both head and tail
                self.try_move(head_row, head_col + 1, tail_row, tail_col + 1)
                self.try_move(head_row + 1, head_col, tail_row + 1, tail_col)

                # Rotate clockwise if there is space and snake is horizontal
                if head_row == tail_row and head_row + 1 < self.grid_size and self.grid[head_row + 1][tail_col] == 0:
                    self.try_move(head_row, head_col, head_row + 1, head_col)

                # Rotate counter-clockwise if there is space and snake is vertical
                if head_col == tail_col and head_col + 1 < self.grid_size and self.grid[tail_row][head_col + 1] == 0:
                    self.try_move(head_row, head_col, head_row, head_col + 1)
            
            steps_count += 1
        
        return -1

    def try_move(self, head_row, head_col, tail_row, tail_col):
        if (0 <= head_row < self.grid_size and 0 <= head_col < self.grid_size and
            0 <= tail_row < self.grid_size and 0 <= tail_col < self.grid_size):
            
            head_pos = head_row * self.grid_size + head_col
            tail_pos = tail_row * self.grid_size + tail_col
            orientation = 0 if head_row == tail_row else 1
            
            if not self.visited_states[head_pos][orientation] and self.grid[head_row][head_col] == 0 and self.grid[tail_row][tail_col] == 0:
                self.bfs_queue.append((head_pos, tail_pos))
                self.visited_states[head_pos][orientation] = True

18000