C++ BFS 50% runtime, 100% memory
BFS, tries for all possible states, tracks which ones have been visited with State\'s id so we don\'t visit those again\n\n\n\'\'\'\nclass Solution {\n    publi
BFS, tries for all possible states, tracks which ones have been visited with State\'s id so we don\'t visit those again\n\n\n\'\'\'\nclass Solution {\n    public:\n        int N;\n    const int dir[4][2] = { {-1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };\n    struct State {\n        int r, c, d, moves, id;\n        State(int r, int c, int d, int moves): r(r), c(c), d(d), moves(moves), id(r * 10000 + c * 100 + d) {}\n    };\n\n    int minimumMoves(vector < vector < int >> & grid) {\n        N = grid.size();\n        int res = INT_MAX;\n        queue < State > que;\n        unordered_set < int > vis;\n        que.push(State(0, 0, 1, 0)); //original state\n        while (!que.empty()) {\n            State curr = que.front();\n            que.pop();\n            int d = curr.d, tr = curr.r, tc = curr.c, hr = tr + dir[d][0], hc = tc + dir[d][1];\n            if (out(tr) || out(tc) || out(hr) || out(hc) || grid[hr][hc] == 1 || grid[tr][tc] == 1 || vis.count(curr.id)) continue; //bad conditions\n            if (reachEnd(curr)) { //yay!\n                res = min(res, curr.moves);\n                continue;\n            }\n            vis.insert(curr.id);\n            que.push(State(tr, tc + 1, d, curr.moves + 1)); //shift right\n            que.push(State(tr + 1, tc, d, curr.moves + 1)); //shift down\n            if (tr == hr && tr != N - 1 && grid[tr + 1][tc] == 0 && grid[hr + 1][hc] == 0) que.push(State(tr, tc, (d + 1) % 4, curr.moves +\n            1)); //horizontal? inbound? both cells below are 0? then rotate clockwise\n            if (tc == hc && tc != N - 1 && grid[tr][tc + 1] == 0 && grid[hr][hc + 1] == 0) que.push(State(tr, tc, (d + 3) % 4, curr.moves +\n            1)); //vertical? inbound? both cells right are 0? rotate ccw\n        }\n        return res == INT_MAX ? -1 : res; //we were never able to reach the end\n    }\n\n    bool out(int curr) {\n        return curr < 0 || curr >= N;\n    }\n\n    bool reachEnd(State curr) {\n        int tr = curr.r, tc = curr.c, hr = tr + dir[curr.d][0], hc = tc + dir[curr.d][1];\n        return tr == N - 1 && hr == N - 1 && hc == N - 1 && tc == N - 2;\n    }\n\n\n};\n\'\'\'
[]