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

namespace details {

    struct Pos {
        int x {};
        int y {};
        constexpr bool operator==(Pos rhs) const {
            return x == rhs.x && y == rhs.y;
        }
    };

    /*
        class invariant: head is adjacent to tail
    */
    struct Snake {
        Pos head {.x = 0, .y = 1};
        Pos tail {.x = 0, .y = 0};
        // note: all snake actions are unchecked for validity
        Snake& move_right() {
            ++head.y, ++tail.y;
            return *this;
        }
        Snake& move_down() {
            ++head.x, ++tail.x;
            return *this;
        }
        Snake& rotate_clockwise() {
            head.x = tail.x + 1, head.y = tail.y;
            return *this;
        }
        Snake& rotate_anticloswise() {
            head.x = tail.x, head.y = tail.y + 1;
            return *this;
        }
        constexpr bool operator==(Snake const& rhs) const {
            return head == rhs.head && tail == rhs.tail;
        }
    };
}

template<>
struct std::hash<details::Snake> {
    std::size_t operator()(details::Snake const& s) const {
        return std::hash<int>{}(
            (s.head.x ^ s.head.y) 
            | ((s.tail.x ^ s.tail.y) << 7)
        );
    }
};

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        using namespace details;
        std::queue<Snake> q;
        q.emplace();
        std::unordered_set<Snake> met {Snake{}};
        
        using snake_action = Snake& (Snake::*)();
        constexpr snake_action actions[4] {
            &Snake::move_down, &Snake::move_right, 
            &Snake::rotate_clockwise, &Snake::rotate_anticloswise
        };

        int n = grid.size();
        auto valid_pos = [&](Pos p) {
            return !(p.x < 0 || p.y < 0 || p.x >= n || p.y >= n) 
                && grid[p.x][p.y] == 0;
        };
        auto valid_move = [&](Snake s, snake_action f)->bool {
            Snake t {s};
            (t.*f)();
            if (!valid_pos(t.head) || !valid_pos(t.tail)) return false;
            if (f == &Snake::rotate_clockwise) {
                Pos below_head {s.head.x+1, s.head.y}, 
                    below_tail {s.tail.x+1, s.tail.y};
                return valid_pos(below_head) && valid_pos(below_tail);
            } else if (f == &Snake::rotate_anticloswise) {
                Pos right_head {s.head.x, s.head.y+1},
                    right_tail {s.tail.x, s.tail.y+1};
                return valid_pos(right_head) && valid_pos(right_tail);
            }
            return true;
        };

        Snake end {{n-1, n-1}, {n-1, n-2}};
        for (int lv {}; !q.empty(); ++lv) {
            int qsize = q.size();
            while (qsize--) {
                Snake curr = q.front(); q.pop();
                for (snake_action act: actions) {
                    if (!valid_move(curr, act)) continue;
                    Snake next {curr};
                    (next.*act)();
                    if (next == end) return lv + 1;
                    if (met.count(next)) continue;
                    met.insert(next);
                    q.push(next);
                }
            }
        }
        return -1;
    }
};
25300