Minimum moves to reach target with rotations

Array Breadth-First Search Matrix

51.9% acceptance

Feb 25, 2026

288

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: Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is. Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is. Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c). Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from (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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_moves(grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::VecDeque;

    let n = grid.len();
    // state: (row, col, dir) where dir=0 horizontal, dir=1 vertical
    // tail at (row, col), head at (row, col+1) if horizontal, (row+1, col) if vertical
    let mut visited = vec![vec![[false; 2]; n]; n];
    visited[0][0][0] = true;
    let mut queue = VecDeque::new();
    queue.push_back((0usize, 0usize, 0usize, 0i32));

    while let Some((r, c, dir, steps)) = queue.pop_front() {
      // Check if reached target
      if r == n - 1 && c == n - 2 && dir == 0 {
        return steps;
      }

      let next_steps = steps + 1;

      if dir == 0 {
        // Horizontal: head at (r, c+1)
        // Move right: new tail (r, c+1), need grid[r][c+2] = 0
        if c + 2 < n && grid[r][c + 2] == 0 && !visited[r][c + 1][0] {
          visited[r][c + 1][0] = true;
          queue.push_back((r, c + 1, 0, next_steps));
        }
        // Move down: new tail (r+1, c), need grid[r+1][c] and grid[r+1][c+1] = 0
        if r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0 && !visited[r + 1][c][0] {
          visited[r + 1][c][0] = true;
          queue.push_back((r + 1, c, 0, next_steps));
        }
        // Rotate clockwise (horizontal -> vertical): tail stays (r, c), need grid[r+1][c] and grid[r+1][c+1] = 0
        if r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0 && !visited[r][c][1] {
          visited[r][c][1] = true;
          queue.push_back((r, c, 1, next_steps));
        }
      } else {
        // Vertical: head at (r+1, c)
        // Move down: new tail (r+1, c), need grid[r+2][c] = 0
        if r + 2 < n && grid[r + 2][c] == 0 && !visited[r + 1][c][1] {
          visited[r + 1][c][1] = true;
          queue.push_back((r + 1, c, 1, next_steps));
        }
        // Move right: new tail (r, c+1), need grid[r][c+1] and grid[r+1][c+1] = 0
        if c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0 && !visited[r][c + 1][1] {
          visited[r][c + 1][1] = true;
          queue.push_back((r, c + 1, 1, next_steps));
        }
        // Rotate counterclockwise (vertical -> horizontal): tail stays (r, c), need grid[r][c+1] and grid[r+1][c+1] = 0
        if c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0 && !visited[r][c][0] {
          visited[r][c][0] = true;
          queue.push_back((r, c, 0, next_steps));
        }
      }
    }
    -1
  }
}