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

class Solution
{
public:

    enum Orientation { North, East, South, West };
    enum Move { Down, Right, RotateCCW, RotateCW };

    Orientation rotateCW(int &r, int &c, Orientation orientation)
    {
        switch (orientation)
        {
            case East:
            --c, ++r;
            return South;

            case South:
            --c, --r;
            return West;

            case West:
            ++c, --r;
            return North;

            case North:
            ++c, ++r;
            return East;
        }
        throw std::runtime_error("Unknown orientation");
    }

    Orientation rotateCCW(int &r, int &c, Orientation orientation) const
    {
        switch (orientation)
        {
            case East:
            --c, --r;
            return North;

            case North:
            --c, ++r;
            return West;

            case West:
            ++c, ++r;
            return South;

            case South:
            ++c, --r;
            return East;
        }
        throw std::runtime_error("Unknown orientation");
    }

    bool isValidMove(int row,
                     int column,
                     Orientation orientation,
                     Move move,
                     std::vector<std::vector<int>> &grid) const
    {
        auto m = grid.size();
        auto n = grid[0].size();
        switch (move)
        {
            case Move::Down:
            switch (orientation)
            {
                case East:
                return (  1 + row < m
                       && column > 0
                       && grid[1 + row][column] == 0
                       && grid[1 + row][column - 1] == 0);

                case North:
                case South:
                return (  1 + row < m
                       && grid[1 + row][column] == 0);

                case West:
                return (  1 + row < m
                       && 1 + column < n
                       && grid[1 + row][column] == 0
                       && grid[1 + row][1 + column] == 0);
            }
            break;

            case Move::Right:
            switch (orientation)
            {
                case East:
                case West:
                return (  1 + column < n
                       && grid[row][1 + column] == 0);

                case North:
                return (  1 + column < n
                       && 1 + row < m
                       && grid[row][1 + column] == 0
                       && grid[1 + row][1 + column] == 0);

                case South:
                return (  1 + column < n
                       && row > 0
                       && grid[row - 1][1 + column] == 0
                       && grid[row][1 + column] == 0);
            }
            break;

            case Move::RotateCCW:
            switch (orientation)
            {
                case East:
                return (  column > 0
                       && row > 0
                       && grid[row - 1][column    ] == 0
                       && grid[row - 1][column - 1] == 0);

                case North:
                return (  column > 0
                       && 1 + row < m
                       && grid[    row][column - 1] == 0
                       && grid[1 + row][column - 1] == 0);

                case South:
                return (  1 + column < n
                       && row > 0
                       && grid[row    ][1 + column] == 0
                       && grid[row - 1][1 + column] == 0);

                case West:
                return (  1 + column < n
                       && 1 + row < m
                       && grid[1 + row][    column] == 0
                       && grid[1 + row][1 + column] == 0);
            }
            break;

            case Move::RotateCW:
            switch (orientation)
            {
                case East:
                return (  column > 0
                       && 1 + row < m
                       && grid[1 + row][column   ] == 0
                       && grid[1 + row][column - 1] == 0);

                case West:
                return (  1 + column < n
                       && row > 0
                       && grid[row - 1][    column] == 0
                       && grid[row - 1][1 + column] == 0);

                case North:
                return (  1 + column < n
                       && 1 + row < m
                       && grid[    row][1 + column] == 0
                       && grid[1 + row][1 + column] == 0);

                case South:
                return (  column > 0
                       && row > 0
                       && grid[row    ][column - 1] == 0
                       && grid[row - 1][column - 1] == 0);
            }
            break;
        }
        return false;
    }

    int minimumMoves(std::vector<std::vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        std::queue<std::tuple<int, int, int, Orientation>> q;
        q.push({ 0, 0, 1, Orientation::East });

        int minMoves = INT_MAX;
        std::vector<std::vector<std::vector<bool>>> visited;
        visited.resize(m, std::vector<std::vector<bool>>(n, std::vector<bool>(4, false)));
        while (!q.empty())
        {
            auto [moves, r, c, orientation] = q.front();
            q.pop();

            if (  moves >= minMoves
               || visited[r][c][orientation])
            {
                continue;
            }
            visited[r][c][orientation] = true;

            if (  (  1 + r == m
                  && 2 + c == n
                  && orientation == Orientation::West)
               || (  1 + r == m
                  && 1 + c == n
                  && orientation == Orientation::East))
            {
                minMoves = std::min(minMoves, moves);
                continue;
            }

            if (isValidMove(r, c, orientation, Move::Down, grid))
            {
                q.push({ 1 + moves, 1 + r, c, orientation });
            }
            
            if (isValidMove(r, c, orientation, Move::Right, grid))
            {
                q.push({ 1 + moves, r, 1 + c, orientation });
            }

            if (  orientation == Orientation::East
               && isValidMove(r, c, orientation, Move::RotateCW, grid))
            {
                auto newRow = r, newColumn = c;
                auto newOrientation = rotateCW(newRow, newColumn, orientation);
                q.push({ 1 + moves, newRow, newColumn, newOrientation });
            }

            if (  orientation == Orientation::South
               && isValidMove(r, c, orientation, Move::RotateCCW, grid))
            {
                auto newRow = r, newColumn = c;
                auto newOrientation = rotateCCW(newRow, newColumn, orientation);
                q.push({ 1 + moves, newRow, newColumn, newOrientation });
            }
        }
        return minMoves == INT_MAX ? -1 : minMoves;
    }
};
32800