Easy BFS C++
We can solve this problem using bfs. In queue of bfs we store 3 things. Snake\'s x coordinate,Snake\'s y coordinate and the direction(true for horizontal, false
We can solve this problem using bfs. In queue of bfs we store 3 things. Snake\'s x coordinate,Snake\'s y coordinate and the direction(true for horizontal, false for vertical). We don\'t need to store head of snake as we can easily find it if we are given these 3 variables.\n\nWe also maintain a visited set of same 3 things(x,y,direction) which will tell us if we have visited the orientation or not. If we have already visited we simply return.\n\nInititally the snake\'s tail is at (0,0) and direction is horizontal so we push (0,0,true) to our queue.\nThen we follow simple bfs and check if we can visit left,right or rotate it and if yes we push it to the queue.\n\nWe need to use two loops for bfs as the inner loop is providing us options in which we can move but eventually we are going to move in just one direction so we have to count whole inner loop once only.\n\n\n```\nclass Solution {\npublic:\n    \n    int n;\n    set<vector<int>> visited;\n    bool candown(vector<vector<int>>& grid,int x,int y,bool hor){\n        if(!hor){\n            if(x+2<n && grid[x+1][y]==0 && grid[x+2][y]==0 && !visited.count({x+1,y,hor})){\n                return true;\n            }\n        }else{\n            if(x+1<n && y+1<n && grid[x+1][y]==0 && grid[x+1][y+1]==0 && !visited.count({x+1,y,hor})){\n                return true;\n            }\n        }\n        \n        return false;\n    }\n    \n    bool canright(vector<vector<int>>& grid,int x,int y,bool hor){\n        if(hor){\n            if(y+2<n && grid[x][y+1]==0 && grid[x][y+2]==0 && !visited.count({x,y+1,hor})){\n                return true;\n            }\n        }else{\n            if(y+1<n && x+1<n && grid[x][y+1]==0 && grid[x+1][y+1]==0 && !visited.count({x,y+1,hor})){\n                return true;\n            }\n        }\n        \n        return false;\n    }\n    \n    bool canrot(vector<vector<int>>& grid,int x,int y,bool hor){\n        if(hor){\n            if(y+1<n && x+1<n && grid[x+1][y]==0 && grid[x+1][y+1]==0 && !visited.count({x,y,!hor})){\n                return true;\n            }\n        }else{\n            if(x+1<n && y+1<n && grid[x][y+1]==0 &&grid[x+1][y+1]==0 && !visited.count({x,y,!hor})){\n                return true;\n            }\n        }\n        return false;\n    }\n    \n    int minimumMoves(vector<vector<int>>& grid) {\n        queue<array<int, 3>> q;\n        q.push({0,0,true});\n        int ans=0;\n        n=grid.size();\n        while(!q.empty()){\n            int size=q.size();\n            while(size--){\n                auto a=q.front();\n                q.pop();\n                if(visited.count({a[0],a[1],a[2]})){\n                    continue;\n                }\n                visited.insert({a[0],a[1],a[2]});\n                int x=a[0];\n                int y=a[1];\n                if(x==n-1 && y==n-2 && a[2]==1){\n                    return ans;\n                }\n                if(candown(grid,x,y,a[2])){\n                    q.push({x+1,y,a[2]});\n                }\n                if(canrot(grid,x,y,a[2])){\n                    q.push({x,y,!a[2]});\n                }\n                if(canright(grid,x,y,a[2])){\n                    q.push({x,y+1,a[2]});\n                }\n            }\n            ans++;\n        }\n        return -1;\n    }\n};\n```\n**Please upvote if you liked the solution.**
['Breadth-First Search', 'Queue', 'C', 'C++']