You are given an $n \times n$ matrix grid, where each cell contains either $0$ indicating an empty cell or $1$ indicating an obstacle.

A snake of length $2$ initially occupies the cells $(0, 0)$ and $(0, 1)$ in a horizontal orientation. The target is for the snake to reach the bottom right position, occupying the cells $(n - 1, n - 2)$ and $(n - 1, n - 1)$ horizontally.

In each move, the snake can perform one of the following actions:

• Move one cell to the right:

  • If the snake is horizontal, both cells must be shifted right by $1$, requiring the cell directly to the right of its head to be empty.

  • If the snake is vertical, both cells must be shifted right by $1$, requiring both cells immediately to the right of its body to be empty.

• Move one cell down:

  • If the snake is horizontal, both cells must be shifted down by $1$, requiring both cells immediately below its body to be empty.

  • If the snake is vertical, both cells must be shifted down by $1$, requiring the cell directly below its head to be empty.

• Rotate clockwise:

  • If the snake is horizontal, it can rotate clockwise around its tail to become vertical, occupying $(r, c)$ and $(r + 1, c)$, provided that the cells $(r + 1, c)$ and $(r + 1, c + 1)$ are both empty.

• Rotate counterclockwise:

  • If the snake is vertical, it can rotate counterclockwise around its tail to become horizontal, occupying $(r, c)$ and $(r, c + 1)$, provided that the cells $(r, c + 1)$ and $(r + 1, c + 1)$ are both empty.

Return the minimum number of moves required to reach the target position, or $-1$ if it is impossible.

Constraints:

• $2 \leq n \leq 100$

• grid.length $== n$

• grid[i].length $== n$

• $0 \leq$ grid[i][j] $\leq 1$

• It is guaranteed that the snake starts at empty cells.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.