[C++] Short BFS (No brainer version)
Observation\nThe two parts of the snake (head and tail) together define it\'s position and thus we need to BFS keeping that in mind.\n\nSolution\nSince this is 
**Observation**\nThe two parts of the snake (head and tail) together define it\'s position and thus we need to BFS keeping that in mind.\n\n**Solution**\nSince this is a no brainer version, we keep track of visited nodes just as regular BFS keeping in mind that 1 node is defined by the 2 positions (Snake\'s head and snake\'s tail).\nSince C++ doesn\'t provide a hash function for a vector by default we can use `set<vector<int>>` (This increases the time complexity) as our way to keep track of visited nodes.\nWe can now run a simle BFS using `queue<vector<int>>` and iterate on all possible neighbours for that node by adding them to the queue and keep repeating until we find the target or the queue gets empty.\n```c++\nclass Solution {\npublic:\n    set<vector<int>> visited;\n    queue<vector<int>> q;\n    void commonMoves(vector<vector<int>>& grid,vector<int> &pos)\n    {\n        if(pos[3]+1<grid.size()&&!grid[pos[2]][pos[3]+1]&&!grid[pos[0]][pos[1]+1]&&!visited.count({pos[0],pos[1]+1,pos[2],pos[3]+1}))     //Move right\n            visited.insert({pos[0],pos[1]+1,pos[2],pos[3]+1}),q.push({pos[0],pos[1]+1,pos[2],pos[3]+1});\n        if(pos[2]+1<grid.size()&&!grid[pos[2]+1][pos[3]]&&!grid[pos[0]+1][pos[1]]&&!visited.count({pos[0]+1,pos[1],pos[2]+1,pos[3]}))       //Move down\n            visited.insert({pos[0]+1,pos[1],pos[2]+1,pos[3]}),q.push({pos[0]+1,pos[1],pos[2]+1,pos[3]});\n    }\n    void horizontal(vector<vector<int>>& grid,vector<int> &pos)\n    {\n        if(pos[0]+1<grid.size()&&!grid[pos[0]+1][pos[1]]&&!grid[pos[2]+1][pos[3]]&&!visited.count({pos[0],pos[1],pos[0]+1,pos[1]}))         //Rotate clockwise\n            visited.insert({pos[0],pos[1],pos[0]+1,pos[1]}),q.push({pos[0],pos[1],pos[0]+1,pos[1]});\n    }\n    void vertical(vector<vector<int>>& grid,vector<int> &pos)\n    {\n        if(pos[1]+1<grid.size()&&!grid[pos[0]][pos[1]+1]&&!grid[pos[2]][pos[3]+1]&&!visited.count({pos[0],pos[1],pos[0],pos[1]+1}))      //Rotate counter-clockwise\n            visited.insert({pos[0],pos[1],pos[0],pos[1]+1}),q.push({pos[0],pos[1],pos[0],pos[1]+1});\n    }\n    int minimumMoves(vector<vector<int>>& grid) \n    {\n        vector<int> target={grid.size()-1,grid.size()-2,grid.size()-1,grid.size()-1}; \n        q.push({0,0,0,1});\n        visited.insert({0,0,0,1});\n        int size,moves=0;\n        while(!q.empty())\n        {\n            size=q.size();\n            while(size--)\n            {\n                if(q.front()==target)                             //Reached target\n                    return moves;\n                if(q.front()[0]==q.front()[2])                 //When snake is horizontal\n                    horizontal(grid,q.front());\n                else                                                   //When snake is vertical\n                    vertical(grid,q.front());\n\t\tcommonMoves(grid,q.front());                 //Common moves (Right and down)\n                q.pop();\n            }\n            moves++;\n        }\n        return -1;\n    }\n};\n```\n**Note**\nTo further reduce the time complexity, we can use an `unordered_set` with a custom implementation of hash function for a vector, this would reduce complexity of adding and searching on `visited` nodes from O(nlogn) to O(n).
[]