Minimum Moves to Reach Target with Rotations

Minimum Moves to Reach Target with Rotations - Problem

In an n×n grid, there is a snake that spans 2 cells and starts at the top-left corner at positions (0, 0) and (0, 1). The grid has empty cells represented by 0 and blocked cells represented by 1.

The snake wants to reach the target at the lower-right corner at positions (n-1, n-2) and (n-1, n-1).

In one move, the snake can:

Move right: Move one cell to the right if there are no blocked cells there
Move down: Move one cell down if there are no blocked cells there
Rotate clockwise: If in horizontal position and the two cells under it are both empty, snake moves from (r, c), (r, c+1) to (r, c), (r+1, c)
Rotate counterclockwise: If in vertical position and the two cells to its right are both empty, snake moves from (r, c), (r+1, c) to (r, c), (r, c+1)

Return the minimum number of moves to reach the target. If there is no way to reach the target, return -1.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[0,0,0,0,0,1],[1,1,0,0,1,0],[0,0,0,0,1,1],[0,0,1,0,1,0],[0,1,1,0,0,0],[0,1,1,0,0,0]]

› Output: 11

💡 Note: Snake starts at (0,0)-(0,1) horizontal and needs to reach (5,4)-(5,5). Through a series of moves and rotations, minimum 11 moves are needed.

Example 2 — Simple Grid

$ Input: grid = [[0,0,1,1,1,1],[0,0,0,0,1,1],[1,1,0,0,0,1],[1,1,1,0,0,0],[0,1,1,0,0,0],[0,1,1,0,0,0]]

› Output: -1

💡 Note: Snake cannot reach the target due to blocked paths, so return -1.

Example 3 — Small Grid

$ Input: grid = [[0,0,0],[0,1,0],[0,0,0]]

› Output: 4

💡 Note: In a 3×3 grid, snake needs 4 moves: right, rotate, down, rotate to reach (2,1)-(2,2).

Constraints

2 ≤ n ≤ 100
grid.length == n
grid[i].length == n
grid[i][j] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

n×n grid with blocked cells (1) and empty cells (0)

Snake Movement

Snake can move right, down, or rotate based on available space

Target Reached

Find minimum moves to reach bottom-right corner

Key Takeaway

🎯 Key Insight: Model snake state as (position + orientation) and use BFS for guaranteed minimum path

Asked in

G Google 15 f Facebook 12 a Amazon 8

This problem requires finding the shortest path for a 2-cell snake in a grid. The key insight is to model each snake configuration as a state (position + orientation) and use BFS to guarantee minimum moves. The snake can move right/down or rotate when conditions allow. Best approach uses BFS with state tracking. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^(n²))	O(n²)	Try all possible move sequences using depth-first search
BFS with State Tracking	O(n²)	O(n²)	Use breadth-first search to find minimum moves by exploring states level by level

Brute Force DFS — Algorithm Steps

Start from initial position (0,0)-(0,1) horizontal
Try each valid move recursively
Return minimum moves among all successful paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Snake at (0,0)-(0,1) horizontal

Recursive Search

Try right, down, rotate from each state

Backtrack

Return minimum moves from all successful paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct State {
    int r1, c1, r2, c2;
    struct State* next;
};

struct State* visited = NULL;

int isVisited(int r1, int c1, int r2, int c2) {
    struct State* curr = visited;
    while (curr) {
        if (curr->r1 == r1 && curr->c1 == c1 && curr->r2 == r2 && curr->c2 == c2) {
            return 1;
        }
        curr = curr->next;
    }
    return 0;
}

void addVisited(int r1, int c1, int r2, int c2) {
    struct State* newState = (struct State*)malloc(sizeof(struct State));
    newState->r1 = r1;
    newState->c1 = c1;
    newState->r2 = r2;
    newState->c2 = c2;
    newState->next = visited;
    visited = newState;
}

void removeVisited(int r1, int c1, int r2, int c2) {
    struct State* curr = visited;
    struct State* prev = NULL;
    
    while (curr) {
        if (curr->r1 == r1 && curr->c1 == c1 && curr->r2 == r2 && curr->c2 == c2) {
            if (prev) {
                prev->next = curr->next;
            } else {
                visited = curr->next;
            }
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

int dfs(int** grid, int n, int r1, int c1, int r2, int c2, int moves) {
    if (r1 == n-1 && c1 == n-2 && r2 == n-1 && c2 == n-1) {
        return moves;
    }
    
    if (isVisited(r1, c1, r2, c2)) {
        return INT_MAX;
    }
    
    addVisited(r1, c1, r2, c2);
    int minMoves = INT_MAX;
    
    // Move right
    if (c2 + 1 < n && grid[r1][c1+1] == 0 && grid[r2][c2+1] == 0) {
        int result = dfs(grid, n, r1, c1+1, r2, c2+1, moves+1);
        if (result != INT_MAX && result < minMoves) {
            minMoves = result;
        }
    }
    
    // Move down
    if (r2 + 1 < n && grid[r1+1][c1] == 0 && grid[r2+1][c2] == 0) {
        int result = dfs(grid, n, r1+1, c1, r2+1, c2, moves+1);
        if (result != INT_MAX && result < minMoves) {
            minMoves = result;
        }
    }
    
    // Rotate clockwise
    if (r1 == r2 && r1 + 1 < n && grid[r1+1][c1] == 0 && grid[r1+1][c2] == 0) {
        int result = dfs(grid, n, r1, c1, r1+1, c1, moves+1);
        if (result != INT_MAX && result < minMoves) {
            minMoves = result;
        }
    }
    
    // Rotate counterclockwise
    if (c1 == c2 && c1 + 1 < n && grid[r1][c1+1] == 0 && grid[r2][c1+1] == 0) {
        int result = dfs(grid, n, r1, c1, r1, c1+1, moves+1);
        if (result != INT_MAX && result < minMoves) {
            minMoves = result;
        }
    }
    
    removeVisited(r1, c1, r2, c2);
    return minMoves;
}

int solution(int** grid, int n) {
    visited = NULL;
    int result = dfs(grid, n, 0, 0, 0, 1, 0);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids
    int n = 3; // Assume 3x3 for simplicity
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse manually for demo
    grid[0][0] = 0; grid[0][1] = 0; grid[0][2] = 0;
    grid[1][0] = 1; grid[1][1] = 1; grid[1][2] = 0;
    grid[2][0] = 0; grid[2][1] = 0; grid[2][2] = 0;
    
    printf("%d\n", solution(grid, n));
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(n²))

Each cell can be visited in 4 states (horizontal/vertical x 2 orientations), leading to exponential branching

⚠ Quadratic Growth

Space Complexity

O(n²)

Recursion stack depth can go up to n² in worst case

⚠ Quadratic Space

32.0K Views

Medium Frequency

~35 min Avg. Time

853 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler