<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:
    
    int dp[101][101][2][2];
    
    int f(int row_index, int column_index, int orientation, int flipped, std::vector<std::vector<int>> &grid)
{
    // std::cout << row_index << " vs " << column_index << " vs " << orientation << std::endl;
    if(orientation == 0 && (row_index == grid.size() - 1) && (column_index == grid.at(0).size() - 2))
    {
        if(grid.at(row_index).at(column_index) == 1 || grid.at(row_index).at(column_index + 1) == 1)
        {
            dp[row_index][column_index][orientation][flipped] = INT_MAX;
            return INT_MAX;
        }
        else
        {
            dp[row_index][column_index][orientation][flipped] = 0;
            return 0;
        }
    }

    if(row_index == grid.size() || column_index == grid.at(0).size())
    {
        return INT_MAX;
    }

    if(orientation == 0 && column_index == grid.at(0).size() - 1)
    {
        return INT_MAX;
    }

    if(orientation == 1 && row_index == grid.size() - 1)
    {
        return INT_MAX;
    }

    if(dp[row_index][column_index][orientation][flipped] != -1)
    {
        return dp[row_index][column_index][orientation][flipped];
    }

    if(orientation == 0 && (grid.at(row_index).at(column_index) == 1 || grid.at(row_index).at(column_index + 1) == 1))
    {
        dp[row_index][column_index][orientation][flipped] = INT_MAX;
        return INT_MAX;
    }

    if(orientation == 1 && (grid.at(row_index).at(column_index) == 1 || grid.at(row_index + 1).at(column_index) == 1))
    {
        dp[row_index][column_index][orientation][flipped] = INT_MAX;
        return INT_MAX;
    }

    int current_recursion_result = INT_MAX;

    int right_recursion_result = f(row_index, column_index + 1, orientation, 0, grid);
    if(right_recursion_result != INT_MAX)
    {
        current_recursion_result = std::min(current_recursion_result, 1 + right_recursion_result);
    }

    int down_recursion_result = f(row_index + 1, column_index, orientation, 0, grid);
    if(down_recursion_result != INT_MAX)
    {
        current_recursion_result = std::min(current_recursion_result, 1 + down_recursion_result);
    }

    if(flipped == 0)
    {
        if(orientation == 0)
        {
            if((row_index < grid.size() - 1))
            {
                if(grid.at(row_index + 1).at(column_index) == 0 && grid.at(row_index + 1).at(column_index + 1) == 0)
                {
                    int rotate_recursion_result = f(row_index, column_index, 1, 1, grid);
                    if(rotate_recursion_result != INT_MAX)
                    {
                        current_recursion_result = std::min(current_recursion_result, 1 + rotate_recursion_result);
                    }
                }
            }
        }
        else
        {
            if(column_index < grid.at(0).size() - 1)
            {
                if(grid.at(row_index).at(column_index + 1) == 0 && grid.at(row_index + 1).at(column_index + 1) == 0)
                {
                    int rotate_recursion_result = f(row_index, column_index, 0, 1, grid);
                    if(rotate_recursion_result != INT_MAX)
                    {
                        current_recursion_result = std::min(current_recursion_result, 1 + rotate_recursion_result);
                    }
                }
            }
        }
    }

    dp[row_index][column_index][orientation][flipped] = current_recursion_result;
    return current_recursion_result;
}
    
    int minimumMoves(vector<vector<int>>& grid) {
        
        for(int i = 0; i <= grid.size(); ++i)
    {
        for(int j = 0; j <= grid.at(0).size(); ++j)
        {
            dp[i][j][0][0] = -1;
            dp[i][j][0][1] = -1;
            dp[i][j][1][0] = -1;
            dp[i][j][1][1] = -1;
        }
    }
        
        int result = f(0, 0, 0, 0, grid);
        if(result == INT_MAX)
        {
            return -1;
        }
        
        return result;
    }
};
14500