Minimum Moves to Reach Target with Rotations: BFS on State Space

You are given an n x n grid of 0s (empty) and 1s (blocked). A snake of length 2 starts horizontal, occupying cells (0, 0) and (0, 1). Your goal is to move it to (n-1, n-2) and (n-1, n-1). Each move, the snake can shift right, shift down, rotate clockwise (horizontal to vertical), or rotate counter-clockwise (vertical to horizontal), as long as the destination cells are within bounds and not blocked. Return the minimum number of moves, or -1 if the target is unreachable.

This is LeetCode 1210: Minimum Moves to Reach Target with Rotations, and it is one of the best problems for learning BFS over an augmented state space. The same technique appears whenever a grid problem has an extra dimension beyond just position.

Why this problem matters

Grid BFS problems usually track (row, col) as the state. But this snake occupies two cells, and it can be horizontal or vertical. That extra dimension (orientation) is what makes this problem interesting. You cannot just track the head's position. You need to track the head's position and which way the snake is facing.

This "BFS with extra state dimensions" pattern shows up in many hard problems. "Open the Lock" (LeetCode 752) uses a 4-digit combination as state. Shortest path problems on layered graphs track (node, keys collected) or (node, remaining fuel). Once you get comfortable adding dimensions to your BFS state, an entire class of problems opens up.

The key insight

Model each state as a triple: (row, col, orientation), where (row, col) is the position of the snake's top-left cell and orientation is either horizontal (0) or vertical (1). From any state, you try up to four transitions:

• Move right: shift the snake one column to the right. Both cells the snake would land on must be empty and in bounds.
• Move down: shift the snake one row down. Same constraint.
• Rotate clockwise (horizontal to vertical): the snake pivots so it goes from occupying (r, c)-(r, c+1) to (r, c)-(r+1, c). This requires (r+1, c) and (r+1, c+1) to be empty (the 2x2 block must be clear).
• Rotate counter-clockwise (vertical to horizontal): the snake pivots from (r, c)-(r+1, c) to (r, c)-(r, c+1). This requires (r, c+1) and (r+1, c+1) to be empty.

BFS over these states guarantees the first time you reach the target state (n-1, n-2, horizontal), you have found the shortest path. Each state is visited at most once, and each transition has cost 1.

The key detail people miss: both rotation directions require checking that the entire 2x2 block is free, not just the destination cells. The snake needs room to pivot.

The solution

from collections import deque

def minimum_moves(grid: list[list[int]]) -> int:
    n = len(grid)
    if grid[n - 1][n - 2] == 1 or grid[n - 1][n - 1] == 1:
        return -1

    visited = set()
    visited.add((0, 0, 0))
    queue = deque([(0, 0, 0, 0)])

    while queue:
        r, c, orient, dist = queue.popleft()

        if r == n - 1 and c == n - 2 and orient == 0:
            return dist

        if orient == 0:
            if c + 2 < n and grid[r][c + 2] == 0:
                if (r, c + 1, 0) not in visited:
                    visited.add((r, c + 1, 0))
                    queue.append((r, c + 1, 0, dist + 1))
            if r + 1 < n and grid[r + 1][c] == 0 and grid[r + 1][c + 1] == 0:
                if (r + 1, c, 0) not in visited:
                    visited.add((r + 1, c, 0))
                    queue.append((r + 1, c, 0, dist + 1))
                if (r, c, 1) not in visited:
                    visited.add((r, c, 1))
                    queue.append((r, c, 1, dist + 1))
        else:
            if r + 2 < n and grid[r + 2][c] == 0:
                if (r + 1, c, 1) not in visited:
                    visited.add((r + 1, c, 1))
                    queue.append((r + 1, c, 1, dist + 1))
            if c + 1 < n and grid[r][c + 1] == 0 and grid[r + 1][c + 1] == 0:
                if (r, c + 1, 1) not in visited:
                    visited.add((r, c + 1, 1))
                    queue.append((r, c + 1, 1, dist + 1))
                if (r, c, 0) not in visited:
                    visited.add((r, c, 0))
                    queue.append((r, c, 0, dist + 1))

    return -1

Here is what each piece does:

1. Early exit: if the goal cells (n-1, n-2) or (n-1, n-1) are blocked, return -1 immediately.

2. State representation: each state is (row, col, orientation) where orientation 0 means horizontal and 1 means vertical. The (row, col) pair always refers to the top-left cell the snake occupies.

3. Horizontal moves: when the snake is horizontal at (r, c)-(r, c+1), moving right checks that column c+2 is in bounds and empty. Moving down checks that both (r+1, c) and (r+1, c+1) are empty. That same "both cells below are empty" check also enables clockwise rotation, so we can enqueue the vertical state (r, c, 1) in the same branch.

4. Vertical moves: when the snake is vertical at (r, c)-(r+1, c), moving down checks that row r+2 is in bounds and (r+2, c) is empty. Moving right checks that both (r, c+1) and (r+1, c+1) are empty. That same check enables counter-clockwise rotation, so we enqueue (r, c, 0).

5. BFS guarantee: since every move costs 1 and we use a FIFO queue, the first time we reach the target state, the distance is minimal.

Visual walkthrough

Let's trace BFS on a 4x4 grid with one blocker at (1, 2). The snake starts at (0, 0) horizontal and needs to reach (3, 2) horizontal.

Each step shows the current snake position, the BFS queue, and which moves are valid. The blocker at (1, 2) forces the snake to find an alternate path, exploring vertical orientations and routing around the obstacle. BFS explores all states at distance d before any at distance d+1, so the first time it hits the goal, the answer is optimal.

Complexity analysis

Time: O(n^2) because there are n * n possible positions for the snake's top-left cell, and 2 orientations, giving 2 * n^2 total states. Each state is enqueued and processed at most once. Each state generates at most 3 neighbors to check. Total work is proportional to the number of states.

Space: O(n^2) for the visited set and the BFS queue. In the worst case, every state is enqueued, which is 2 * n^2 entries. The grid itself is also n^2, so space is dominated by the state storage.

Edge cases

• Goal cells blocked: if grid[n-1][n-2] or grid[n-1][n-1] is 1, return -1 immediately.
• Start cells blocked: the problem guarantees (0, 0) and (0, 1) are empty, but it is good practice to check.
• No path exists: BFS exhausts all reachable states without finding the target. Return -1.
• n = 2: the grid is 2x2. The snake starts at (0, 0)-(0, 1) and the goal is (1, 0)-(1, 1). One move down is enough, if the bottom row is clear.
• Snake must rotate to navigate: some grids require the snake to switch between horizontal and vertical to fit through narrow corridors.
• Large empty grid: the snake can go straight down then straight right. BFS finds this in O(n) moves, but still visits O(n^2) states in the worst case.

The building blocks

1. BFS on an implicit graph

The grid itself is not the graph. The state space is the graph. Each node is (row, col, orientation), and edges connect states that differ by one valid move. You never build this graph explicitly. Instead, you generate neighbors on the fly inside the BFS loop. This is the same pattern used in "Open the Lock," "Sliding Puzzle," and any problem where the search space is too large to materialize but each state has a small number of neighbors.

2. State representation with extra dimensions

Adding orientation to the BFS state is the core technique. Without it, you would lose track of whether the snake is horizontal or vertical, and you could not determine which moves are legal. This generalizes: whenever a grid problem has an extra property that affects movement (keys collected, fuel remaining, time parity), add that property as another dimension to your state tuple. The BFS algorithm stays identical. Only the state definition and neighbor generation change.

From understanding to recall

You have seen how to model a two-cell snake on a grid as a BFS over (row, col, orientation) states. The logic splits neatly: horizontal states try move-right, move-down, and rotate-CW; vertical states try move-down, move-right, and rotate-CCW. The 2x2 block check for rotations is bundled with the directional move check.

The details that trip people up are the bounds checks and the rotation preconditions. Is it c + 2 or c + 1? Do you check one cell or two? These are not conceptual misunderstandings. They are precision problems, and they show up under time pressure.

Spaced repetition is how you lock in the details. You practice writing the state transitions from memory at increasing intervals until the pattern is automatic. When you see "grid BFS with extra state" in a problem description, the template comes out cleanly.

Related posts

• Shortest Path in Binary Matrix - BFS on a grid to find the shortest path, the foundation this problem builds on
• Number of Islands - Grid traversal fundamentals with DFS/BFS flood fill
• Open the Lock - BFS over an implicit state graph with combination states

CodeBricks breaks this problem into its BFS state-space modeling and rotation-checking building blocks, then drills them independently with spaced repetition. You write each piece from scratch until the pattern is automatic. When a multi-dimensional BFS problem appears in your interview, you do not hesitate. You just write it.