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] <= 1The key idea for #1210 Minimum Moves to Reach Target with Rotations is to model the snake's position and orientation as a state and explore the grid using Breadth-First Search (BFS). Each state represents the coordinates of the snake's head and tail (or equivalently the tail position and orientation). BFS works well because every move—shifting right, shifting down, or rotating—has equal cost, and we want the minimum number of moves.
From each state, generate all valid transitions: moving horizontally, moving vertically, or rotating if the surrounding cells are empty. Use a visited structure to avoid revisiting the same configuration of position and orientation. The search continues level by level until the snake reaches the target configuration.
This approach systematically explores the grid while ensuring the first time the target is reached corresponds to the minimum number of moves. The algorithm typically runs in O(n²) time due to the bounded number of states and BFS traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search with state (position + orientation) | O(n^2) | O(n^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use BFS to find the answer.
The state of the BFS is the position (x, y) along with a binary value that specifies if the position is horizontal or vertical.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
BFS is preferred because the problem asks for the minimum number of moves. Since each move has equal weight, BFS ensures that the first time the target configuration is reached corresponds to the shortest sequence of moves.
Yes, this type of problem is common in FAANG-style interviews because it tests BFS, grid traversal, and state representation. It also evaluates a candidate's ability to model complex movements and transitions in matrix-based problems.
The optimal approach uses Breadth-First Search (BFS) to explore all valid snake states in the grid. Each state represents the snake's position and orientation, and BFS guarantees the minimum number of moves because each transition has equal cost.
A queue is ideal for implementing BFS since it processes states level by level. Additionally, a visited set or matrix is required to track previously explored snake configurations and avoid redundant exploration.