In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).
In one move the snake can:
(r, c) and (r, c+1) to (r, c) and (r+1, c).
(r, c) and (r+1, c) to (r, c) and (r, c+1).
Return the minimum number of moves to reach the target.
If there is no way to reach the target, return -1.
Example 1:
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
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].
Example 2:
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,1], [1,1,1,0,0,1], [1,1,1,0,0,0]] Output: 9
Constraints:
2 <= n <= 1000 <= grid[i][j] <= 1Problem Overview: You control a 2‑cell snake inside an n x n grid. The snake can move right, move down, or rotate between horizontal and vertical positions if the surrounding cells are empty. The goal is to reach the bottom‑right target configuration using the minimum number of moves.
Approach 1: State Graph BFS (O(n2) time, O(n2) space)
The grid can be treated as a graph where each node represents the snake's state: the head position and its orientation (horizontal or vertical). From each state, generate valid transitions: move right, move down, or rotate if the required cells are free. Use Breadth-First Search to explore states level by level, since BFS guarantees the first time you reach the target configuration is the minimum number of moves. Maintain a visited set keyed by (row, col, orientation) to avoid revisiting the same configuration. The total number of states is at most 2 * n * n, giving O(n2) time and O(n2) space.
Approach 2: BFS with State Encoding and Transition Pruning (O(n2) time, O(n2) space)
This version keeps the same BFS idea but encodes the snake using the top‑left cell of the segment plus orientation. That representation avoids storing both cells explicitly and simplifies transition checks. When horizontal, you attempt: right shift, down shift, and clockwise rotation. When vertical, you attempt: down shift, right shift, and counter‑clockwise rotation. Each transition checks the required cells in the matrix to ensure they are within bounds and empty. Using a compact visited structure such as a boolean 3D array improves cache locality and keeps the BFS fast even when the grid is large.
The algorithm relies heavily on graph traversal concepts from Breadth-First Search and grid state modeling using arrays. Once the state representation is correct, transitions become straightforward conditional checks.
Recommended for interviews: The BFS state‑graph solution is the expected approach. Interviewers want to see how you model the snake configuration as a graph node and generate valid transitions. A naive exploration without visited tracking quickly explodes in states, while the BFS with state encoding shows strong problem‑modeling and graph traversal skills.
Breadth-First Search (BFS) is a powerful technique for such grid-based traversal problems. The idea is to explore all potential moves that the snake can make from its current position and orientation, tracking the number of moves. Each state of the snake (defined by its head position and orientation) is enqueued with its move count. This ensures that the shortest path to the goal is found first, making BFS ideal for finding the minimum number of moves.
This solution uses BFS. The queue holds tuples representing the head and tail of the snake along with the current number of moves. For each state, potential moves are checked (right, down, and rotations), and new states are added to the queue if they haven't been visited yet.
Python
C++
Java
JavaScript
Time Complexity: O(n^3), because in the worst case, for each of n^2 possible states on the n*n grid, we process it in multiple directions.
Space Complexity: O(n^3), because of the growth in the queue and visited data structures.
The problem asks for the minimum number of moves for the snake to reach the target position from the starting position. We consider using Breadth-First Search (BFS) to solve it.
We define the following data structures or variables:
q: Stores the current position of the snake. Each position is a tuple (a, b), where a represents the tail position of the snake, and b represents the head position of the snake. Initially, we add the position (0, 1) to the queue q. If we flatten the 2D maze into a 1D array, then the position (0, 1) represents the two cells with indices 0 and 1 in the 1D array.target: The value is fixed at (n^2 - 2, n^2 - 1), which is the last two cells of the last row of the 2D maze.vis: Stores whether the current position state of the snake has been visited. Each state is a tuple (a, status), where a represents the tail position of the snake, and status represents the current state of the snake, with values of 0 or 1, representing the horizontal and vertical states of the snake, respectively. Initially, add the state of the starting position (0, 1) to the set vis.ans: Stores the number of moves for the snake to reach the target position from the starting position. Initially, it is 0.We use BFS to solve it. Each time we take a position from the queue q, we check whether the position is the target position target. If it is, we directly return the answer variable ans. If not, we add the next possible position of this position to the queue q and add this position to vis. Note that the next position could be the horizontal or vertical state of the snake, and we need to judge them separately (see the following code comments). At the end of each round of search, the answer variable ans increments by 1.
Finally, if the queue q is empty, it means that it is impossible to reach the target position from the starting position, so return -1.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of rows or columns of the 2D maze.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Breadth-First Search | Time Complexity: O(n^3), because in the worst case, for each of n^2 possible states on the n*n grid, we process it in multiple directions. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive BFS without state pruning | Exponential | High | Conceptual understanding of transitions; not practical for large grids |
| BFS with (row, col, orientation) state | O(n^2) | O(n^2) | General optimal solution for finding minimum moves in the grid |
| BFS with compact state encoding | O(n^2) | O(n^2) | Production or interview code where efficient state checks and clean transitions matter |
Minimum Moves to Reach Target with Rotations | BFS Algorithm Explained in JavaScript | LeetCode • Coding theory • 1,098 views views
Watch 5 more video solutions →Practice Minimum Moves to Reach Target with Rotations with our built-in code editor and test cases.
Practice on FleetCode