Minimum Moves To Reach Target With Rotations - Leetcode Solution

Problem Statement: Given a NxN grid, each cell of which contains values 0, 1 or 2. You start from the top-left corner and reach the bottom-right corner. Only two types of moves are allowed:

You can either move to the cell to your right(noting there is no cell to the right of the last column) or You can rotate 90 degrees clockwise and move to the cell that is now in the direction of the right. Return the minimum number of moves required to reach the bottom-right corner.

Solution: We will use BFS (breadth first search) to solve this problem.

First, we need to create a state class, which will store the current position, direction and the number of moves taken to reach this state.

Then we will create a queue and add the starting state to it. In each iteration of the loop, we will dequeue the front state, generate all the possible next states from the current state, and check if any of the next states is the target state. If we find the target state, we return the number of moves taken to reach that state. Otherwise, we add all the next states to the queue and continue with the next iteration.

Generating next possible states: We can generate the next possible states by either moving right or rotating and then moving right. If we move right, we just need to check if the cell to the right is valid and has not been visited yet. If we rotate and then move right, we need to check if the new cell after rotation is valid and has not been visited yet.

We will use a set to keep track of visited states. We will add a state to the set as soon as we enqueue it in the queue.

To keep track of the direction, we will use four different integers:

0: right 1: down 2: left 3: up

We will use modulo arithmetic to change the direction when rotating.

Code: Here is the implementation of the above approach in python:

from typing import List

class State: def init(self, row: int, col: int, direction: int, moves: int): self.row = row self.col = col self.direction = direction self.moves = moves

def minimumMoves(grid: List[List[int]]) -> int: n = len(grid) start = State(0, 0, 0, 0) # starting state target = State(n-1, n-1, 0, 0) # target state

queue = [start]
visited = set([start])

while queue:
    curr_state = queue.pop(0)
    
    # check if we have reached the target state
    if curr_state.row == target.row and curr_state.col == target.col:
        return curr_state.moves
    
    # generate all possible next states
    for dr, dc, dd in [(0, 1, 0), (1, 0, 1), (0, -1, 2), (-1, 0, 3)]: # move right, down, left, up
        
        # if we are moving in the same direction
        nr, nc = curr_state.row + dr, curr_state.col + dc
        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] != 1:
            next_state = State(nr, nc, curr_state.direction, curr_state.moves+1)
            if next_state not in visited:
                queue.append(next_state)
                visited.add(next_state)
        
        # if we are rotating 90 degrees and then moving right
        if dd != curr_state.direction:
            nr, nc = curr_state.row, curr_state.col
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] != 1:
                for i in range(3):
                    nr, nc = nc, n-1-nr # rotate 90 degrees
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] != 1:
                        next_state = State(nr, nc, dd, curr_state.moves+1)
                        if next_state not in visited:
                            queue.append(next_state)
                            visited.add(next_state)

return -1 # target state is unreachable

Time Complexity: The time complexity of this algorithm is O(n^2), where n is the size of the grid. This is because each cell can be visited at most once.

Space Complexity: The space complexity of this algorithm is O(n^2), because of the visited set.

1