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

enum class Pos { kHorizontal, kVertical };

class Solution {
 public:
  int minimumMoves(vector<vector<int>>& grid) {
    const int n = grid.size();
    int ans = 0;
    // the state of (x, y, pos)
    // pos := 0 (horizontal) / 1 (vertical)
    queue<tuple<int, int, Pos>> q{{{0, 0, Pos::kHorizontal}}};
    vector<vector<vector<bool>>> seen(n,
                                      vector<vector<bool>>(n, vector<bool>(2)));
    seen[0][0][static_cast<int>(Pos::kHorizontal)] = true;

    auto canMoveRight = [&](int x, int y, Pos pos) -> bool {
      if (pos == Pos::kHorizontal)
        return y + 2 < n && !grid[x][y + 2];
      return y + 1 < n && !grid[x][y + 1] && !grid[x + 1][y + 1];
    };

    auto canMoveDown = [&](int x, int y, Pos pos) -> bool {
      if (pos == Pos::kVertical)
        return x + 2 < n && !grid[x + 2][y];
      return x + 1 < n && !grid[x + 1][y] && !grid[x + 1][y + 1];
    };

    auto canRotateClockwise = [&](int x, int y, Pos pos) -> bool {
      return pos == Pos::kHorizontal && x + 1 < n && !grid[x + 1][y + 1] &&
             !grid[x + 1][y];
    };

    auto canRotateCounterclockwise = [&](int x, int y, Pos pos) -> bool {
      return pos == Pos::kVertical && y + 1 < n && !grid[x + 1][y + 1] &&
             !grid[x][y + 1];
    };

    while (!q.empty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [x, y, pos] = q.front();
        q.pop();
        if (x == n - 1 && y == n - 2 && pos == Pos::kHorizontal)
          return ans;
        if (canMoveRight(x, y, pos) && !seen[x][y + 1][static_cast<int>(pos)]) {
          q.emplace(x, y + 1, pos);
          seen[x][y + 1][static_cast<int>(pos)] = true;
        }
        if (canMoveDown(x, y, pos) && !seen[x + 1][y][static_cast<int>(pos)]) {
          q.emplace(x + 1, y, pos);
          seen[x + 1][y][static_cast<int>(pos)] = true;
        }
        const Pos newPos =
            pos == Pos::kHorizontal ? Pos::kVertical : Pos::kHorizontal;
        if ((canRotateClockwise(x, y, pos) ||
             canRotateCounterclockwise(x, y, pos)) &&
            !seen[x][y][static_cast<int>(newPos)]) {
          q.emplace(x, y, newPos);
          seen[x][y][static_cast<int>(newPos)] = true;
        }
      }
      ++ans;
    }

    return -1;
  }
};
29700