PYTHON | 100 % FASTEST SOL | BFS + HASHMAP | FULLY EXPLAINED |
Runtime: 233 ms, faster than 100.00% of Python3 online submissions for Minimum Moves to Reach Target with Rotations.\n# Memory Usage: 16 MB, less than 56.06% of
# Runtime: 233 ms, faster than 100.00% of Python3 online submissions for Minimum Moves to Reach Target with Rotations.\n# Memory Usage: 16 MB, less than 56.06% of Python3 online submissions for Minimum Moves to Reach Target with Rotations.\n\n# EXPLANATION\nThe idea is very simple \nKeep track of the cell of head of the snake as well as the direction head is facing\n\n\nWhen snake is positioned horizontally:\n1. we can move right\n2. we can move down\n3. make snake vertical\n\nWhen snake is positioned vertically:\n1. we can move right\n2. we can move down\n3. make snake vertical\n\n\nSince there can be multiple solutions possible and we need solution with minimum numbers of steps we use BFS\n\nOnce a cell is visited in a direction we don\'t visit the cell in the same direction again to avoid \nrepeatition\n# CODE\n```\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        queue , vis , n = [(0,1,0,0)] , {} , len(grid)\n        while queue:\n            x,y,pos,moves = queue.pop(0)\n            if x == y == n-1 and pos == 0: return moves\n            if pos == 0:\n                if y + 1 < n and grid[x][y+1] == 0 and (x,y+1,0) not in vis:\n                    vis[(x,y+1,0)] = True\n                    queue.append((x,y+1,0,moves+1))\n                \n                if x + 1 < n and grid[x+1][y-1] == 0 and grid[x+1][y] == 0:\n                    if (x+1,y-1,1) not in vis:\n                        vis[(x+1,y-1,1)] = True\n                        queue.append((x+1,y-1,1,moves+1))\n                    if (x+1,y,0) not in vis:\n                        vis[(x+1,y,0)] = True\n                        queue.append((x+1,y,0,moves+1))\n            else:\n                if x + 1 < n and grid[x+1][y] == 0 and (x+1,y,1) not in vis:\n                    vis[(x+1,y,1)] = True\n                    queue.append((x+1,y,1,moves+1))\n                if y + 1 < n and grid[x-1][y+1] == grid[x][y+1] == 0:\n                    if (x-1,y+1,0) not in vis:\n                        vis[(x-1,y+1,0)] = True\n                        queue.append((x-1,y+1,0,moves+1))\n                    if (x,y+1,1) not in vis:\n                        vis[(x,y+1,1)] = True\n                        queue.append((x,y+1,1,moves+1))\n        return -1\n```
['Breadth-First Search', 'Python', 'Python3']