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

using grid = std::vector<std::vector<int>>;
using vi = std::vector<std::vector<std::vector<bool>>>;
using dist = std::vector<std::vector<std::vector<int>>>;
using cell = std::pair<int, int>;
using state = std::pair<cell, int>;

class Solution {
private:
    enum Pos { H = 0, V = 1 };
    const int inf = 5 * 1e+05;
    const int Empty = 0;
    const int Block = 1;
    int M, N;
    vi visited;
    dist distance;
    bool checkBoundary(int y, int x)
    { return y >= 0 && y < M && x >= 0 && x < N; }
    bool checkHorizontalRightMove(const grid& g, const state& s) 
    {
        int y = s.first.first;
        int x = s.first.second + 1; // head
        return checkBoundary(y, x) && !visited[H][y][x] && g[y][x] == Empty;
    }
    bool checkVerticalRightMove(const grid& g, const state& s) 
    {
        int head_y = s.first.first;
        int head_x = s.first.second + 1;
        int tail_y = s.first.first - 1;
        int tail_x = s.first.second + 1;
        return 
          checkBoundary(head_y, head_x) &&
          checkBoundary(tail_y, tail_x) && 
          !visited[V][head_y][head_x] && 
          !visited[V][tail_y][tail_x] && 
          g[head_y][head_x] == Empty &&
          g[tail_y][tail_x] == Empty;
    }
    bool checkHorizontalDownMove(const grid& g, const state& s)
    {
        int head_y = s.first.first + 1;
        int head_x = s.first.second;
        int tail_y = s.first.first + 1;
        int tail_x = s.first.second - 1;
        return 
          checkBoundary(head_y, head_x) &&
          checkBoundary(tail_y, tail_x) && 
          !visited[H][head_y][head_x] && 
          !visited[H][tail_y][tail_x] &&
          g[head_y][head_x] == Empty && 
          g[tail_y][tail_x] == Empty;
    }
    bool checkVerticalDownMove(const grid& g, const state& s) 
    {
        int y = s.first.first + 1;
        int x = s.first.second;
        return checkBoundary(y, x) && !visited[V][y][x] && g[y][x] == Empty;
    }
    bool checkClockwiseMove(const grid& g, const state& s) 
    {
        int y = s.first.first + 1;
        int x = s.first.second - 1;
        int aux_below_y = s.first.first + 1;
        int aux_below_x = s.first.second;
        return 
          checkBoundary(y, x) &&
          checkBoundary(aux_below_y, aux_below_x) && 
          !visited[V][y][x] &&
          g[y][x] == Empty &&
          g[aux_below_y][aux_below_x] == Empty;
    }
    bool checkCounterClockwiseMove(const grid& g, const state& s) 
    {
        int y = s.first.first - 1;
        int x = s.first.second + 1;
        int aux_right_y = s.first.first;
        int aux_right_x = s.first.second + 1;
        return 
          checkBoundary(y, x) && 
          checkBoundary(aux_right_y, aux_right_x) && 
          !visited[H][y][x] &&
          g[y][x] == Empty && 
          g[aux_right_y][aux_right_x] == Empty;
    }
    void bfs(const grid& g, std::queue<state> q)
    {
        while(!q.empty())
        {
            state s = q.front();
            q.pop();
            int curr_y = s.first.first;
            int curr_x = s.first.second;
            int p = s.second;
            if(p == H && checkHorizontalRightMove(g, s))
            {
                //  If the snake is horizontal, move the head to (r, c + 1)
                int y = curr_y;
                int x = curr_x + 1; // head
                visited[H][y][x] = true;
                distance[H][y][x] = distance[p][curr_y][curr_x] + 1;
                q.push({{y, x}, H});

            } //... 
            if(p == V && checkVerticalRightMove(g, s))
            {
                // If the snake is vertical, you can move both the head and tail to the next column in one step. 
                // Head to (r, c + 1), tail to (r - 1, c + 1)
                int head_y = curr_y;
                int head_x = curr_x + 1;
                int tail_y = curr_y - 1;
                int tail_x = curr_x + 1;
                visited[V][head_y][head_x] = 
                visited[V][tail_y][tail_x] = true;
                distance[V][head_y][head_x] = distance[p][curr_y][curr_x] + 1;
                q.push({{head_y, head_x}, V});

            } //...
            if(p == H && checkHorizontalDownMove(g, s))
            {
                // If the snake is horizontal, you can move both the head and tail to the next row in one step. 
                // Head to (r + 1, c), tail to (r + 1, c - 1)
                int head_y = curr_y + 1;
                int head_x = curr_x;
                int tail_y = curr_y + 1;
                int tail_x = curr_x - 1;
                visited[H][head_y][head_x] = 
                visited[H][tail_y][tail_x] = true;
                distance[H][head_y][head_x] = distance[p][curr_y][curr_x] + 1;
                q.push({{head_y, head_x}, H});

            } //...
            if(p == V && checkVerticalDownMove(g, s))
            {
                 // If the snake is vertical, move the head to (r + 1, c)
                 int y = curr_y + 1;
                 int x = curr_x;
                 visited[V][y][x] = true;
                 distance[V][y][x] = distance[p][curr_y][curr_x] + 1;
                 q.push({{y, x}, V});

            } //...
            if(p == H && checkClockwiseMove(g, s))
            {
                 // Move the head to (r + 1, c - 1)
                 int y = curr_y + 1;
                 int x = curr_x - 1;
                 int aux_y = curr_y + 1;
                 int aux_x = curr_x;
                 visited[V][y][x] = true;
                //  visited[H][aux_y][aux_x] = true;
                 distance[V][y][x] = distance[p][curr_y][curr_x] + 1;
                 q.push({{y, x}, V});                 

            } //...
            if(p == V && checkCounterClockwiseMove(g, s))
            {
                 // Move the head to (r - 1, c + 1)
                 int y = curr_y - 1;
                 int x = curr_x + 1;
                 int aux_y = curr_y;
                 int aux_x = curr_x + 1;
                 visited[H][y][x] = true;
                //  visited[H][aux_y][aux_x] = true;
                 distance[H][y][x] = distance[p][curr_y][curr_x] + 1;
                 q.push({{y, x}, H});
            } //...
        }
    }
public:
    int minimumMoves(vector<vector<int>>& g) 
    {
        M = g.size();
        N = g[0].size();
        std::queue<state> q;
        visited = vi(2, std::vector<std::vector<bool>>(M, std::vector<bool>(N, false))); // 2 cells occupied
        distance = dist(2, std::vector<std::vector<int>>(M, std::vector<int>(N, inf))); // only head cell counts
        q.push({{0, 1}, H});
        visited[H][0][0] = true;
        visited[H][0][1] = true;
        distance[H][0][1] = 0;
        bfs(g, q);
        int ans = distance[H][M - 1][N - 1];
        return ans != inf ? ans : -1;    
    }
};
20400