[C++] simple BFS
Approach\nUsual BFS where graph vertices are described by the following struct\n\nstruct Position {\n    vector<int> a; //tail of the snake\n    vector<int> b; 
# Approach\nUsual BFS where graph vertices are described by the following struct\n```\nstruct Position {\n    vector<int> a; //tail of the snake\n    vector<int> b; //head\n}\n``` \nTo keep track of visited vertices, use a hash function.\n\n# Complexity\n- Time complexity: $$O(nm)$$\n\n- Space complexity: $$O(nm)$$\n\n# Code\n```\nusing lli = long long int;\nconst lli base = 101;\nconst lli mod = 1e9+7;\n\nstruct Position {\n    vector<int> a;\n    vector<int> b;\n};\n\nbool ver(Position& pos) {\n    return (pos.b[0]-pos.a[0] == 1);\n}\n\nbool hor(Position& pos) {\n    return (pos.b[1]-pos.a[1] == 1);\n}\n\nlli myhash(Position& pos) {\n    lli k = 1;\n    lli h = 0;\n    for (int x : pos.a) {\n        h = (h + k*((lli)x))%mod;\n        k = (k*base)%mod;\n    }\n    for (int x : pos.b) {\n        h = (h + k*((lli)x))%mod;\n        k = (k*base)%mod;\n    }\n    return h; \n}\n\n\nclass Solution {\npublic:\n    int minimumMoves(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        function<vector<Position>(Position&)> neighbors = [&](Position& pos) -> vector<Position> {\n            vector<Position> res;\n            Position down = pos;\n            down.a[0]++;\n            down.b[0]++;\n            if (down.a[0] < m && down.b[0] < m && grid[down.a[0]][down.a[1]] == 0 && grid[down.b[0]][down.b[1]] == 0) {\n                res.push_back(down);\n                if (hor(pos)) res.push_back({pos.a, {pos.a[0]+1, pos.a[1]}}); \n            }\n            Position right = pos;\n            right.a[1]++;\n            right.b[1]++; \n            if (right.a[1] < n && right.b[1] < n && grid[right.a[0]][right.a[1]] == 0 && grid[right.b[0]][right.b[1]] == 0) {\n                res.push_back(right);\n                if (ver(pos)) res.push_back({pos.a, {pos.a[0], pos.a[1]+1}}); \n            }\n            return res;\n        };\n        unordered_map<lli,int> dist;\n        deque<Position> q(1, {{0,0},{0,1}});\n        dist[myhash(q[0])] = 0; \n        while(!q.empty()) {\n            Position pos = q[0];\n            lli curh = myhash(q[0]); \n            q.pop_front();\n            vector<Position> ngh = neighbors(pos);\n            for (Position& nxt : ngh) {\n                lli h = myhash(nxt);\n                if (dist.find(h) == dist.end()) {\n                    dist[h] = dist[curh]+1;\n                    q.push_back(nxt); \n                }\n            }\n        }\n        Position t = {{n-1, n-2}, {n-1, n-1}}; \n        lli th = myhash(t);\n        if (dist.find(th) == dist.end()) return -1;\n        return dist[th]; \n    }\n};\n```
['C++']