<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:
// time: O(n*n)
// space: O(n*n)
    int minimumMoves(vector<vector<int>>& grid) {
      const int n = grid.size();  

      const auto get_key = [n](int r, int c) {
        return r * n + c;
      };
      
      const auto get_pos = [n](int key) {
        return pair<int, int>{key / n, key % n};
      };

      // head key v.s. tail key.
      queue<pair<int, int>> q;
      const int head = get_key(0, 1);
      const int tail = get_key(0, 0);
      q.emplace(head, tail);

      unordered_map<int, unordered_set<int>> seen;
      seen[head].emplace(tail);

      int step = 0;
      while (!q.empty()) {
        int size = q.size();
        while (size --) {
          const auto [head_key, tail_key] = q.front();
          q.pop();
          const auto [r_h, c_h] = get_pos(head_key);
          const auto [r_t, c_t] = get_pos(tail_key);
          if (r_t == n - 1 && c_t == n - 2 && r_h == n - 1 && c_h == n - 1) {
            return step;
          }

          // move right.
          bool move_right = true;
          // row does not change. 
          if (c_h + 1 == n || c_t + 1 == n || grid[r_h][c_h + 1] == 1 || grid[r_t][c_t + 1] == 1) {
            move_right = false;
          }
          if (move_right) {
            const int h_key = get_key(r_h, c_h + 1);
            const int t_key = get_key(r_t, c_t + 1);
            if (!(seen.count(h_key) && seen[h_key].count(t_key))) {
              seen[h_key].emplace(t_key);
              q.emplace(h_key, t_key);
            }
          }

          // move down.
          bool move_down = true;
          // col does not change.
          if (r_h + 1 == n || r_t + 1 == n || grid[r_h + 1][c_h] == 1 || grid[r_t + 1][c_t] == 1) {
            move_down = false;
          }
          if (move_down) {
            const int h_key = get_key(r_h + 1, c_h);
            const int t_key = get_key(r_t + 1, c_t);
            if (seen.count(h_key) && seen[h_key].count(t_key)) {
              continue;
            }
            seen[h_key].emplace(t_key);
            q.emplace(h_key, t_key);
          }

          // rotate.
          if (r_h == r_t) {
            bool clockwise = true;
            // rotate clockwise.
            if (r_h + 1 == n || grid[r_h + 1][c_h] == 1 || grid[r_h + 1][c_t] == 1) {
              clockwise = false;
            }
            if (clockwise) {
              const int h_key = get_key(r_h + 1, c_t);
              if (!(seen.count(h_key) && seen[h_key].count(tail_key))) {
                seen[h_key].emplace(tail_key);
                q.emplace(h_key, tail_key);
              }
            }
          } else if (c_h == c_t) {
            // counter clockwise.
            bool counter_clock = true;
            if (c_h + 1 == n || grid[r_t][c_h + 1] == 1 || grid[r_h][c_h + 1] == 1) {
              counter_clock = false;
            }
            if (counter_clock) {
              const int h_key = get_key(r_t, c_h + 1);
              if (!(seen.count(h_key) && seen[h_key].count(tail_key))) {
                seen[h_key].emplace(tail_key);
                q.emplace(h_key, tail_key);
              }
            }
          }
        }

        ++ step;
      }

      return -1;
    }
};
39800