[Python] BFS - Annotated
Legend:\nr, c : current row/column\nR, C : number of rows/columns in grid\nd : the distance the snake has traveled\nq : queue that stores (distance traveled to 
**Legend:**\nr, c : current row/column\nR, C : number of rows/columns in grid\nd : the distance the snake has traveled\nq : queue that stores (distance traveled to current position (d), current row (r), curren column (c), orientation (o))\no : orientation (0 is horizontal and 1 is vertical) - please forgive the use of o as a variable name\n\n**Notes:**\nNothing too out of the oridnary here as far as BFS goes.  The exception being that visited contains two dictionaries.  \n\nBoth dictionaries keep track of how far the snake traveled (d) to get to the location (r,c).  However, the first one only records when the snake is in the horizontal position, and the second one only records when the snake is in the vertical position.  \n\nBecause the snake must reach the finish in the horizontal position, we check visited[0][target] to see if the snake made it to the finish, and how many "steps" it took.\n\n```python\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        \n        self.grid = grid\n        self.R, self.C = len(grid), len(grid[0])\n        target = (self.R-1, self.C-1)\n        \n        q = [(0,0,1,0)]           #(distance traveled, row, column, orientation)\n        visited = [{(0,1): 0},{}] #visited in horizontal state, visited in vertical state\n        \n        while q:\n            \n            d, r, c, o = heapq.heappop(q)\n            \n            #Check if snake can shift down, shift right, or rotate\n            shift_d, shift_r, rot = self.shift_down(r,c,o), self.shift_right(r,c,o), self.rotate(r,c,o)\n            \n            #increment distance traveled by 1\n            d += 1\n            \n            #Update the queue and visited after the snake has shifted down, right, or rotated\n            if shift_d:\n                i,j = shift_d\n                if d < visited[o].get((i,j),float(\'inf\')):\n                    visited[o][(i,j)] = d\n                    heapq.heappush(q,(d,i,j,o))\n                    \n            if shift_r:\n                i,j = shift_r\n                if d < visited[o].get((i,j),float(\'inf\')):\n                    visited[o][(i,j)] = d\n                    heapq.heappush(q,(d,i,j,o))\n                    \n            if rot:\n                i,j = rot\n                if d < visited[1-o].get((i,j),float(\'inf\')):\n                    visited[1-o][(i,j)] = d\n                    heapq.heappush(q,(d,i,j,1-o))\n            \n        return visited[0].get(target,-1)\n    \n    \n    def shift_right(self, r, c, orient):\n        \'\'\'returns False if snake cannot move to the right, otherwise returns new head position\'\'\'\n        if (orient == 0) and ((c == self.C-1) or self.grid[r][c+1]): return False\n        if (orient == 1) and ((c == self.C-1) or self.grid[r][c+1] or self.grid[r-1][c+1]): return False\n        return (r, c+1)\n\n    def shift_down(self, r, c, orient):\n        \'\'\'returns False if snake cannot move downwards, otherwise returns new head position\'\'\'\n        if (orient == 1) and ((r == self.R-1) or self.grid[r+1][c]): return False\n        if (orient == 0) and ((r == self.R-1) or self.grid[r+1][c] or self.grid[r+1][c-1]): return False\n        return (r+1, c)\n    \n    def rotate(self, r, c, orient):\n        \'\'\'returns False if the snake is blocked from rotating, otherwise returns new head position (r,c)\'\'\'\n        #horizontal to vertical CW rotation\n        if (orient == 0) and ((r == self.R-1) or self.grid[r+1][c] or self.grid[r+1][c-1]): return False\n        if (orient == 0): return (r+1,c-1)\n        \n        #vertical to horizontal CCW rotation\n        if (c == self.C-1) or self.grid[r][c+1] or self.grid[r-1][c+1]: return False\n        return (r-1,c+1) \n```
['Breadth-First Search', 'Python']