Python BFS solution with explaination
hx and hy refer to x and y of the head, tx and ty refer to x and y of the tail. For each move, we check if the two blocks under the snake are available (if the 
hx and hy refer to x and y of the head, tx and ty refer to x and y of the tail. For each move, we check if the two blocks under the snake are available (if the snake is in vertical direction, then the block under the tail is always available). If so, we can choose either to rotate in clockwise direction, or to move downward for one cell. Similarly, we check the two cells to the right of the snake, and let the snake rotate counterclockwise or move rightward.\n\nNote: the tuple in seen represents the postion of (x of the snake head, y of the snake head, x of the snake tail, y of the snake tail). Once the snake has already reach a position, it is not necessary for the snake to visit it again. Maybe bits manipulation could save more space for my solution.\n```\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        q = collections.deque([(0,0,1,0,0)])\n        seen = {(0,1,0,0)}\n        while q:\n            t, hx, hy, tx, ty = q.popleft()\n            if hx == hy == tx == n - 1 and ty == n - 2:\n                return t\n            #Check the ceils under the snake\n            if hx + 1 < n and not grid[hx + 1][hy] and not grid[tx + 1][ty]:\n                #try to move downward\n                if (hx + 1, hy, tx + 1, ty) not in seen:\n                    q += (t + 1, hx + 1, hy, tx + 1, ty),\n                    seen.add((hx + 1, hy, tx + 1, ty))\n                #try to rotate clockwise\n                if tx == hx and (tx + 1, ty, tx, ty) not in seen:\n                    q += (t + 1, tx + 1, ty, tx, ty),\n                    seen.add((tx + 1, ty, tx, ty))\n            #Check the ceils to the right\n            if hy + 1 < n and not grid[hx][hy + 1] and not grid[tx][1 + ty]:\n                #try to move rightward\n                if (hx, 1 + hy, tx, 1 + ty) not in seen:\n                    q +=(t + 1, hx, 1 + hy, tx, 1 + ty),\n                    seen.add((hx, hy + 1, tx, 1 + ty))\n                #try to rotate counterclockwise\n                if ty == hy and (tx, ty + 1, tx, ty) not in seen:\n                    q += (t + 1, tx, ty + 1, tx, ty),\n                    seen.add((tx, 1 + ty, tx, ty))\n        return -1
[]