Python BFS solution
\n\nfrom collections import deque\n\nclass Snake(object):\n    def __init__(self, x = 0, y = 0 , orientation=0):\n        self.x = x\n        self.y = y\n      
\n```\nfrom collections import deque\n\nclass Snake(object):\n    def __init__(self, x = 0, y = 0 , orientation=0):\n        self.x = x\n        self.y = y\n        self.orientation = orientation\n        self.num_moves = 0\n        self.prev_move = \'\'\n        self.visited = {(0,0,0)}\n        \n    def move(self, move):\n        if move == \'r\':\n            self.y += 1\n        elif move == \'d\':\n            self.x += 1\n        elif move == \'cw\':\n            self.orientation = 1\n        elif move == \'ccw\':\n            self.orientation = 0\n        else:\n            assert 0, "Undefined move"\n        \n        if (self.x, self.y, self.orientation) in self.visited:\n            return 1\n        \n        self.visited.add((self.x, self.y, self.orientation))\n        \n        self.num_moves += 1\n            \n    def is_target(self, n):\n        if self.x == n-1 and self.y == n - 2 and self.orientation == 0:\n            return True\n        return False\n    \n    def get_info(self):\n        return (self.x, self.y, self.orientation, self.num_moves, self.visited)\n\n    def set_info(self, info):\n        self.x, self.y, self.orientation, self.num_moves, self.visited = info\n        \n    \n\nclass Solution(object):\n    def minimumMoves(self, grid):\n        """\n        :type grid: List[List[int]]\n        :rtype: int\n        """\n        self.grid = grid\n        self.n = len(grid)\n        \n        # moves = [\'r\', \'d\', \'cw\', \'ccw\']   \n        snake = Snake()\n        \n        m = self._get_allowed_moves(snake)\n        q = deque(m)\n        qinf = deque([snake.get_info()]*len(m))\n\n        while q:\n            m = q.popleft()\n            info = qinf.popleft()\n            snake.set_info(info)\n            visited = snake.move(m)\n            if visited: continue\n\n            m = self._get_allowed_moves(snake)\n            q.extend(m)\n            qinf.extend([snake.get_info()]*len(m))\n            \n            if snake.is_target(self.n):\n                return snake.num_moves\n\n        return -1\n            \n        \n    def _get_allowed_moves(self, snake):\n        allowed_move = []\n        \n        if snake.orientation==0:\n            if snake.y+2<self.n and self.grid[snake.x][snake.y+2]==0:\n                allowed_move.append(\'r\')\n            if snake.x+1<self.n and self.grid[snake.x+1][snake.y]==0 and self.grid[snake.x+1][snake.y+1]==0:\n                allowed_move.append(\'d\')\n                allowed_move.append(\'cw\')\n                \n        if snake.orientation==1:\n            if snake.y+1<self.n and self.grid[snake.x][snake.y+1]==0 and self.grid[snake.x+1][snake.y+1]==0:\n                allowed_move.append(\'r\')\n                allowed_move.append(\'ccw\')\n            if snake.x+2<self.n and self.grid[snake.x+2][snake.y]==0:\n                allowed_move.append(\'d\')\n                \n        return allowed_move\n\n```
[]