<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 {
    struct Position {
        int r;
        int c;
        bool h;

        auto operator<=>(Position const&) const = default;
    };

public:
    int minimumMoves(std::vector<std::vector<int>> const& grid) {
        int const n = std::size(grid);
        auto const allMoves = [&](Position const p) {
            auto const free = [&](int const r, int const c) {
                return r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == 0;
            };
            std::vector<Position> moves;
            if (p.h && free(p.r, p.c + 2) || !p.h && free(p.r, p.c + 1) && free(p.r + 1, p.c + 1)) {
                moves.push_back(Position{p.r, p.c + 1, p.h});
            }
            if (p.h && free(p.r + 1, p.c) && free(p.r + 1, p.c + 1) || !p.h && free(p.r + 2, p.c)) {
                moves.push_back(Position{p.r + 1, p.c, p.h});
            }
            if (p.h && free(p.r + 1, p.c) && free(p.r + 1, p.c + 1) || !p.h && free(p.r, p.c + 1) && free(p.r + 1, p.c + 1)) {
                moves.push_back(Position{p.r, p.c, !p.h});
            }
            return moves;
        };
        std::set<Position> enqueued;
        std::queue<std::pair<Position, int>> queue;
        auto const enqueue = [&](auto move, auto const steps) {
            enqueued.insert(move);
            queue.push({std::move(move), steps});
        };
        queue.push({{0, 0, true}, 0});
        while (!queue.empty()) {
            auto const [p, steps] = queue.front();
            queue.pop();
            if (p.r == n - 1 && p.c == n - 2 && p.h) {
                return steps;
            }
            for (auto const move : allMoves(p)) {
                if (enqueued.count(move) == 0) {
                    enqueue(move, steps + 1);
                }
            }
        };
        return -1;
    }
};
36800