Watch 6 video solutions for Minimum Moves to Reach Target with Rotations, a hard level problem involving Array, Breadth-First Search, Matrix. This walkthrough by Coding theory has 1,098 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |