BFS : check visited for the snake's head and direction
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // 1 : horizontal\n    // 2 : vertical\n    int minimumMoves(vector<vector<int>>& g) {\n        int n = g.size();\n        queue<vector<int>> q; // head pos - direction\n        vector<vector<vector<bool>>> vs(n, vector<vector<bool>>(n, vector<bool>(3, false)));\n        int ans = 0;\n        q.push({0, 1, 1});\n        vs[0][1][1] = true;\n        while (!q.empty()) {\n            int sz = q.size();\n            while (sz--) {\n                int r = q.front()[0];\n                int c = q.front()[1];\n                int dir = q.front()[2];\n                q.pop();\n                if (r == n-1 && c == n-1 && dir == 1) return ans;\n                if (dir == 1) { // horizontal\n                    // go right\n                    if (c + 1 < n && g[r][c+1] == 0 &&  !vs[r][c+1][1]) {\n                        vs[r][c+1][1] = true;\n                        q.push({r, c+1, 1});\n                    }\n                    // rotate clockwise\n                    if (r + 1 < n && g[r+1][c-1] == 0 && g[r+1][c] == 0 && !vs[r + 1][c-1][2]) {\n                        vs[r+1][c-1][2] = true;\n                        q.push({r+1, c-1, 2});\n                    }\n                    // go down\n                    if (r + 1 < n && g[r+1][c-1] == 0 && g[r+1][c] == 0 && !vs[r + 1][c][1]) {\n                        vs[r+1][c][1] = true;\n                        q.push({r+1, c, 1});\n                    }                    \n                } else { // vertical\n                    // go down\n                    if (r + 1 < n && g[r+1][c] == 0 && !vs[r+1][c][2]) {\n                        vs[r+1][c][2] = true;\n                        q.push({r+1, c, 2});\n                    }\n                    // rotate counterclockwise\n                    if (c+1 < n && g[r][c+1] == 0 && g[r-1][c+1] ==0 && !vs[r-1][c+1][1]) {\n                        vs[r-1][c+1][1] = true;\n                        q.push({r-1, c+1, 1});\n                    }\n                    // go right\n                    if (c+1 < n && g[r][c+1] == 0 && g[r-1][c+1] ==0 && !vs[r][c+1][2]) {\n                        vs[r][c+1][2] = true;\n                        q.push({r, c+1, 2});\n                    }                    \n                }\n\n            }\n            ans++;\n        }\n        return -1;;\n    }\n};\n```
['Breadth-First Search', 'C++']