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.

**Solution:**

Djikstra. Postions as nodes, nodes connect if one postion can move to another position. Used a threshold to separate vertical and horizontal case.

```
int sep = 10000;
int INF = 1000000000;
int n;
class Solution {
public:
bool valid(int x, int y, vector<vector<int>>& grid){
return (x >= 0 && x<n && y>=0 && y<n && grid[x][y] == 0);
}
int minimumMoves(vector<vector<int>>& grid) {
n = grid.size();
vector<int> dist(20001, INF);
priority_queue<pair<int,int>> pq;
dist[1] = 0;
pq.push(make_pair(0,1));
while(!pq.empty()){
pair<int,int> cur = pq.top();
pq.pop();
if(cur.first > dist[cur.second]) continue;
int i = cur.second;
dist[i] = cur.first;
int xh,yh,xt,yt;
if(i >= sep){
xh = (i-sep)/n;
yh = (i-sep)%n;
xt = xh-1;
yt = yh;
// cout<<xh<<" "<<yh<<" V:"<<dist[i];
if(valid(xh,yh+1, grid) && valid(xt,yt+1,grid) && dist[i+1] > dist[i]+1) pq.push(make_pair(dist[i]+1,i+1));
if(valid(xh+1,yh, grid) && dist[i+n] > dist[i]+1) pq.push(make_pair(dist[i]+1,i+n));
if(valid(xt, yh+1, grid) && valid(xh,yh+1, grid) && dist[i-sep-n+1] > dist[i]+1) pq.push(make_pair(dist[i]+1,i-sep-n+1));
}else{
xh = i/n;
yh = i%n;
xt = xh;
yt = yh-1;
// cout<<xh<<" "<<yh<<" H:"<<dist[i];
if(valid(xh,yh+1, grid) && dist[i+1] > dist[i]+1) pq.push(make_pair(dist[i]+1,i+1));
if(valid(xh+1,yh, grid) && valid(xh+1, yt, grid) && dist[i+n] > dist[i]+1) pq.push(make_pair(dist[i]+1,i+n));
if(valid(xt+1, yt, grid) && valid(xh+1, yh, grid) && dist[i+sep+n-1] > dist[i]+1) pq.push(make_pair(dist[i]+1,i+sep+n-1));
}
}
return (dist[n*n-1] == INF)?-1:dist[n*n-1];
}
};
```