Super Fast And Readable Python Solution Using Breadth First Search
Intuition\nThis looks like a variation of the basic path planning problem where we must navigate a grid with obstacles. These are classically solved with breadt
# Intuition\nThis looks like a variation of the basic path planning problem where we must navigate a grid with obstacles. These are classically solved with breadth first search BFS as BFS reveals the shortest path to a node the very first time you reach it.\n\nThe twist here is that we have a snake that takes up two squares instead of the usual one. This slightly complicates the graph representation of the problem.\n\n# Approach\nWe create a graph as follows:\n* A vertex V is a triple of the form (row, column, orientation) where orientation is 0 if the snake is horizontal and 1 if the snake is vertical. As an example (3, 5, 0) means that the snake is taking up grid positions (3, 5) and (3, 6) and (3, 5, 1) means that the snake is taking up grid positions (3, 5) and (4, 5).\n* A directed edge exists between two vertices V1 and V2 if it is possible to go from V1 to V2 with a single move (right, down, clockwise rotation, or counter-clockwise rotation).\n* The resulting graph G can be more easily represented by its two subgraphs GH and GV with each consisting of horizontally- and vertically-oriented vertices. We create two matrices Hnodes and Vnodes to store the minimum distance to each node. A sentinel value of infinity (inf) is used to represent nodes that have not been reached yet. If a node remains infinity after the algorithm terminates, then it is unreachable via the allowed moves.\n* Now apply a BFS traversal of G using a queue.\n\nNote that as of this writing, this solution was the fastest running submission and also the submission using the least memory.\n\n\n# Complexity\n- Time complexity:\n$O(n^2)$ where $n$ is the length of the side of the square grid. Note that general BFS can be much slower, especially for densely connected graphs; however, we take advantage of the fact the local connectedness topology.\n\n- Space complexity:\n$O(n^2)$ from the matrices we used to store distances.\n\n# Code\n```\nfrom collections import deque\n\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        inf = 10000\n        N = len(grid)\n        Hnodes = [[inf for col in range(N-1)] for row in range(N)]\n        Vnodes = [[inf for col in range(N)] for row in range(N-1)]\n        nodeQueue = deque()\n\n        # Starting position\n        Hnodes[0][0] = 0\n        nodeQueue.append((0, 0, 0)) # row, col, orientation\n\n        while len(nodeQueue) > 0:\n            node = nodeQueue.popleft()\n            row = node[0]\n            col = node[1]\n            orientation = node[2]\n            # horizontal case\n            if orientation == 0:\n                minMoves = Hnodes[row][col]\n                # move right case\n                if col + 2 < N and grid[row][col + 2] == 0 and Hnodes[row][col + 1] == inf:\n                    Hnodes[row][col + 1] = minMoves + 1\n                    nodeQueue.append((row, col + 1, 0))\n                # move down case or rotate clockwise case\n                if row + 1 < N and grid[row + 1][col] == 0 and grid[row + 1][col + 1] == 0:\n                    # move down\n                    if Hnodes[row + 1][col] == inf:\n                        Hnodes[row + 1][col] = minMoves + 1\n                        nodeQueue.append((row + 1, col, 0))\n                    # rotate clockwise\n                    if Vnodes[row][col] == inf:\n                        Vnodes[row][col] = minMoves + 1\n                        nodeQueue.append((row, col, 1))\n            # vertical case\n            else:\n                minMoves = Vnodes[row][col]\n                # move down case\n                if row + 2 < N and grid[row + 2][col] == 0 and Vnodes[row + 1][col] == inf:\n                    Vnodes[row + 1][col] = minMoves + 1\n                    nodeQueue.append((row + 1, col, 1))\n                # move right or rotate counter clockwise case\n                if col + 1 < N and grid[row][col + 1] == 0 and grid[row + 1][col + 1] == 0:\n                    # move right\n                    if Vnodes[row][col + 1] == inf:\n                        Vnodes[row][col + 1] = minMoves + 1\n                        nodeQueue.append((row, col + 1, 1))\n                    # rotate counter clockwise\n                    if Hnodes[row][col] == inf:\n                        Hnodes[row][col] = minMoves + 1\n                        nodeQueue.append((row, col, 0))\n\n        minDist = Hnodes[N - 1][N - 2]\n        return minDist if minDist < inf else -1\n```
['Python3']