<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>

struct snake{
    int x1, y1,  x2,  y2;
    snake(int x1, int y1, int x2, int y2){
        this->x1 = x1;
        this->x2 = x2;
        this->y1 = y1;
        this->y2 = y2;
    }
    bool operator<(const snake& other) const {
        if (x1 != other.x1) return x1 < other.x1;
        if (y1 != other.y1) return y1 < other.y1;
        if (x2 != other.x2) return x2 < other.x2;
        return y2 < other.y2;
    }
};

class Solution {
public:
    // x2, y2 where mouth is
    vector<snake> get_moves(vector<vector<int>> &grid, snake &sn){
        int n = grid.size();
        vector<snake> ans;
        int y2 = sn.y2;
        int y1 = sn.y1, x1=  sn.x1, x2 = sn.x2;
        if(sn.x1 == sn.x2){
            if(y2 + 1 < n and grid[x1][y2+1] == 0){
                ans.push_back(snake(x2, y2, x2, y2+1));
            }
            if(x1 + 1 < n and grid[x1+1][y1] == 0 and grid[x1+1][y2] == 0){
                ans.push_back(snake(x1, y1, x1+1, y1));
                ans.push_back(snake(x1+1, y1, x2+1, y2));
            }

        }  
        else if(sn.y1 == sn.y2){
            if(x2 + 1 < n and grid[x2+1][y2] == 0){
                ans.push_back(snake(x2, y2, x2+1, y2));
            }
            if(y1 + 1 < n and grid[x1][y1+1] == 0 and grid[x2][y1+1] == 0){
                ans.push_back(snake(x1, y1, x1, y1+1));
                ans.push_back(snake(x1, y1+1, x2, y1+1));
            }
        } 
        return ans;
    }
    int minimumMoves(vector<vector<int>>& grid)
    {
        int n = grid.size();
        queue<snake> q;
        map<snake, int> mp;
        snake sn(0,0,0,1);
        q.push(sn);
        mp[sn] = 0;
        while(!q.empty()){
            auto x = q.front();
            // cout << x.x1 << " " << x.y1 << " " << x.x2 << " " << x.y2 << endl;
            q.pop();
            vector<snake> mvs = get_moves(grid, x);
            for(auto it:mvs){
                if(!mp.count(it)){
                    q.push(it);
                    mp[it] = mp[x] + 1;
                }
            }
        }
        snake fina(n-1, n-2, n-1, n-1);
        return mp.count(fina) ? mp[fina] : -1;
    }
};
42900