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

using namespace std;
struct Coord {
    int x;
    int y;
};

string Hash(Coord const& c) {
    return to_string(c.x) + "," + to_string(c.y);
}

struct SnakePos {
    Coord c;
    bool vert;
    int steps;
};

using Grid = vector<vector<int>>;

string Hash(SnakePos const& p) {
    return Hash(p.c) + "," + to_string((int)p.vert);
}

bool inBounds(SnakePos const& p, Grid const& g) {
    int w = g[0].size();
    int h = g.size();
    if (p.vert) { // check bottom
        if (p.c.y + 1 >= h || p.c.x >= w) return false;
    } else {
        if (p.c.x + 1 >= w || p.c.y >= h) return false;
    }
    return true;
}

bool validLocation(SnakePos const& p, Grid const& g) {
    Coord c2;
    if (p.vert) {
        c2 = {p.c.x, p.c.y + 1};
    } else {
        c2 = {p.c.x + 1, p.c.y};
    }
    return g[p.c.y][p.c.x] == 0 && g[c2.y][c2.x] == 0;
}

bool shiftRight(SnakePos& p, Grid const& g) {
    p.c.x += 1;
    if (inBounds(p, g) && validLocation(p, g)) {
        return true;
    } else {
        p.c.x -= 1;
        return false;
    }
}

bool shiftDown(SnakePos& p, Grid const& g) {
    p.c.y += 1;
    if (inBounds(p, g) && validLocation(p, g)) {
        return true;
    } else {
        p.c.y -= 1;
        return false;
    }
}

bool found(SnakePos const& p, int w, int h) {
    return !p.vert && p.c.x == w - 2 && p.c.y == h - 1;
}

bool rotate(SnakePos& p, Grid const& g) {
    if (p.c.y == g.size() - 1 || p.c.x == g[0].size() - 1) return false;
    vector<Coord> coords = {p.c, {p.c.x, p.c.y + 1}, {p.c.x + 1, p.c.y}, {p.c.x + 1, p.c.y + 1}};
    for (const auto& c : coords) {
        if (g[c.y][c.x] == 1) return false;
    }
    p.vert = !p.vert;
    return true;
}

class Solution {
public:
    int minimumMoves(Grid& grid) {
        int w = grid[0].size();
        int h = grid.size();
        SnakePos p = {{0,0}, false, 0};
        unordered_set<string> visited;
        queue<SnakePos> q;
        q.push(p);
        auto transforms = {shiftRight, shiftDown, rotate};
        while (!q.empty()) {
            auto p = q.front(); q.pop();
            if (found(p, h, w)) return p.steps;
            cout << Hash(p) << endl;
            if (visited.find(Hash(p)) != visited.end()) continue;
            visited.insert(Hash(p));
            for (auto t : transforms) {
                auto pCpy = p;
                pCpy.steps += 1;
                if (t(pCpy, grid)) q.push(pCpy);
            }
        }
        return -1;
    }
};
37300