In an&nbsp;n*n&nbsp;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&nbsp;(n-1, n-2)&nbsp;and&nbsp;(n-1, n-1).

In one move the snake can:


	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.
	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.
	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&nbsp;(r, c)&nbsp;and&nbsp;(r, c+1)&nbsp;to&nbsp;(r, c)&nbsp;and&nbsp;(r+1, c).
	
	Rotate counterclockwise&nbsp;if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from&nbsp;(r, c)&nbsp;and&nbsp;(r+1, c)&nbsp;to&nbsp;(r, c)&nbsp;and&nbsp;(r, c+1).
	


Return the minimum number of moves to reach the target.

If there is no way to reach the target, return&nbsp;-1.

&nbsp;
Example 1:



Input: 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]]
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],
&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]]
Output: 9


&nbsp;
Constraints:


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


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        queue , vis , n = [(0,1,0,0)] , {} , len(grid)
        while queue:
            x,y,pos,moves = queue.pop(0)
            if x == y == n-1 and pos == 0: return moves
            if pos == 0:
                if y + 1 < n and grid[x][y+1] == 0 and (x,y+1,0) not in vis:
                    vis[(x,y+1,0)] = True
                    queue.append((x,y+1,0,moves+1))
                
                if x + 1 < n and grid[x+1][y-1] == 0 and grid[x+1][y] == 0:
                    if (x+1,y-1,1) not in vis:
                        vis[(x+1,y-1,1)] = True
                        queue.append((x+1,y-1,1,moves+1))
                    if (x+1,y,0) not in vis:
                        vis[(x+1,y,0)] = True
                        queue.append((x+1,y,0,moves+1))
            else:
                if x + 1 < n and grid[x+1][y] == 0 and (x+1,y,1) not in vis:
                    vis[(x+1,y,1)] = True
                    queue.append((x+1,y,1,moves+1))
                if y + 1 < n and grid[x-1][y+1] == grid[x][y+1] == 0:
                    if (x-1,y+1,0) not in vis:
                        vis[(x-1,y+1,0)] = True
                        queue.append((x-1,y+1,0,moves+1))
                    if (x,y+1,1) not in vis:
                        vis[(x,y+1,1)] = True
                        queue.append((x,y+1,1,moves+1))
        return -1
class Solution {
    public int minimumMoves(int[][] grid) {
        
        int n = grid.length;  
        //boolean[][][][] visited = new boolean[n][n][n][n];
        Set<Position> set = new HashSet<>();
       
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(0,0,0,1));        
        int count = 0;
                
        if(grid[n-1][n-2] == 1 || grid[n-1][n-1] == 1)
            return -1;
        
        while(!q.isEmpty()){
            ++count;
            Queue<Position> nextq = new LinkedList<>();
            while(!q.isEmpty()){
                
                Position p = q.poll();

                int r1 = p.getr1();
                int r2 = p.getr2();
                int c1 = p.getc1();
                int c2 = p.getc2();
                
                if(r1 == n-1 && r2 == n-1 && c1 == n-2 && c2==n-1)
                    return count-1;
                
                if(set.contains(p))
                    continue;
                
                if(c1+1 < n && grid[r1] [c1+1] != 1 && c2+1 < n && grid[r2] [c2+1] != 1)
                    nextq.offer(new Position(r1, c1+1, r2, c2+1));
                if(r1+1 < n && grid[r1+1] [c1] != 1 && r2+1 < n && grid[r2+1] [c2] != 1)
                    nextq.offer(new Position(r1+1, c1, r2+1, c2));
                
                if(r1 == r2 && r1+1 < n && r2+1 < n && grid[r1+1][c1] == 0 && grid[r2+1][c2] == 0 && grid[r1+1][c1] == 0)
                    nextq.offer(new Position(r1,c1, r1+1, c1));
                
                if(c1 == c2 && c1+1 < n && c2+1 < n && grid[r1][c1+1] == 0 && grid[r2][c1+1] == 0   && grid[r1][c1+1] == 0)
                    nextq.offer(new Position(r1,c1, r1, c1+1));
                set.add(p);
            }
            q = nextq;
        }
        return -1;
    }
    
    private class Position{
        int r1;
        int c1;
        int r2;
        int c2;
        
        public Position(int r1, int c1, int r2, int c2){
            this.r1 = r1;
            this.r2 = r2;
            this.c1 =c1;
            this.c2 = c2;
        }
        
        public int getr1(){
            return this.r1;
        }
        public int getr2(){
            return this.r2;
        }
        public int getc1(){
            return this.c1;
        }
        public int getc2(){
            return this.c2;
        }
        
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * r1 + c1 + prime *r2 + c2;
            return result;
        }
        
        @Override
        public boolean equals(Object obj) {
            Position p = (Position) obj;
            if(this.r1 == p.getr1() && this.r2 ==p.getr2() && this.c1 == p.getc1() && this.c2==p.getc2())
                return true;
            else
                return false;
        }
    }    
}
class Solution {

public:

int n;
set<vector<int>> visited;
bool candown(vector<vector<int>>& grid,int x,int y,bool hor){
    if(!hor){
        if(x+2<n && grid[x+1][y]==0 && grid[x+2][y]==0 && !visited.count({x+1,y,hor})){
            return true;
        }
    }else{
        if(x+1<n && y+1<n && grid[x+1][y]==0 && grid[x+1][y+1]==0 && !visited.count({x+1,y,hor})){
            return true;
        }
    }

    return false;
}

bool canright(vector<vector<int>>& grid,int x,int y,bool hor){
    if(hor){
        if(y+2<n && grid[x][y+1]==0 && grid[x][y+2]==0 && !visited.count({x,y+1,hor})){
            return true;
        }
    }else{
        if(y+1<n && x+1<n && grid[x][y+1]==0 && grid[x+1][y+1]==0 && !visited.count({x,y+1,hor})){
            return true;
        }
    }

    return false;
}

bool canrot(vector<vector<int>>& grid,int x,int y,bool hor){
    if(hor){
        if(y+1<n && x+1<n && grid[x+1][y]==0 && grid[x+1][y+1]==0 && !visited.count({x,y,!hor})){
            return true;
        }
    }else{
        if(x+1<n && y+1<n && grid[x][y+1]==0 &&grid[x+1][y+1]==0 && !visited.count({x,y,!hor})){
            return true;
        }
    }
    return false;
}

int minimumMoves(vector<vector<int>>& grid) {
    queue<array<int, 3>> q;
    q.push({0,0,true});
    int ans=0;
    n=grid.size();
    while(!q.empty()){
        int size=q.size();
        while(size--){
            auto a=q.front();
            q.pop();
            if(visited.count({a[0],a[1],a[2]})){
                continue;
            }
            visited.insert({a[0],a[1],a[2]});
            int x=a[0];
            int y=a[1];
            if(x==n-1 && y==n-2 && a[2]==1){
                return ans;
            }
            if(candown(grid,x,y,a[2])){
                q.push({x+1,y,a[2]});
            }
            if(canrot(grid,x,y,a[2])){
                q.push({x,y,!a[2]});
            }
            if(canright(grid,x,y,a[2])){
                q.push({x,y+1,a[2]});
            }
        }
        ans++;
    }
    return -1;
}
};
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumMoves = function(grid) {
    const len = grid.length;
    const initPosition = [0, true, 1]
    const visited = new Set([initPosition.join()]);

    const queue = new Queue();
    initPosition.push(0);
    queue.enqueue(initPosition)
    while (!queue.isEmpty()) {
        let [row, isHorizontal, col, numMoves] = queue.dequeue();
        if (row + col === len * 2 - 2 && isHorizontal) return numMoves;
        numMoves++;
        const positions = [];
        if (isHorizontal) {
            if (grid[row][col + 1] === 0) {
                positions.push([row, true, col + 1])
            }
            if (row + 1 < len && grid[row + 1][col - 1] === 0 && grid[row + 1][col] === 0) {
                positions.push([row + 1, true, col])
                positions.push([row + 1, false, col - 1]);
            }
        } else {
            if (row + 1 < len && grid[row + 1][col] === 0) {
                positions.push([row + 1, false, col]);
            }
            if (row > 0 && grid[row - 1][col + 1] === 0 && grid[row][col + 1] === 0) {
                positions.push([row, false, col + 1]);
                positions.push([row - 1, true, col + 1]);
            }
        }
        for (let position of positions) {
            const str = position.join();
            if (visited.has(str)) continue;
            visited.add(str);
            position.push(numMoves);
            queue.enqueue(position);
        }
    }
    return -1;
};

class Queue {
    constructor() {
        this.head = { next: null };
        this.tail = this.head;
    }

    isEmpty() {
        return this.head.next === null;
    }

    dequeue() {
        const { value } = this.head.next;
        this.head = this.head.next;
        return value;
    }

    enqueue(value) {
        this.tail.next = { value, next: null };
        this.tail = this.tail.next;
    }
}
Minimum Moves to Reach Target with Rotations