Problem statement

https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/

Solution

In this problem we need to return the minimum number of moves, so we should use bfs. Here the state is the following (x, y, dr), where (x, y) are coordinates of tail and dr is direction of snake - either 0 or 1. Then each time we try to make move we check:

  1. If we can move in the same direction, for this we need to make sure that we have free cell in from of snake.
  2. To make move perpendicular to its direction (either snake is horizontal and we move to the down or shake is vertical and we move to the right), then we need two empty cells avaliable.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def minimumMoves(self, grid):
        def check(x, y): return x < n and y < n and grid[x][y] == 0
        
        n = len(grid)
        queue = deque([(0, 0, 0, 0)])
        V = {(0, 0, 0)}
        
        while queue:
            steps, x, y, dr = queue.popleft()
            if (x, y, dr) == (n-2, n-1, 0): return steps
            cands = []
            if check(y+2*dr, x+2-2*dr):
                cands.append((x+1-dr, y+dr, dr))
            if check(y+1, x+1) and grid[y+1-dr][x+dr] == 0:
                cands.append((x+dr, y+1-dr, dr))
                cands.append((x, y, 1-dr))    
                
            for cand in cands:
                if cand not in V:
                    V.add(cand)
                    queue.append((steps+1,) + cand)
        
        return -1