Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1210. Minimum Moves to Reach Target with Rotations - Leetcode Solution

Code Implementation

from collections import deque

class Solution:
    def minimumMoves(self, grid):
        n = len(grid)
        # Each state: (tail_x, tail_y, orientation), 0 = horizontal, 1 = vertical
        queue = deque()
        visited = set()
        # Start: tail at (0,0), horizontal (0), head at (0,1)
        queue.append((0, 0, 0, 0))  # x, y, orientation, moves
        visited.add((0, 0, 0))
        while queue:
            x, y, orient, moves = queue.popleft()
            # Target: tail at (n-1, n-2), horizontal
            if x == n-1 and y == n-2 and orient == 0:
                return moves
            # Move forward
            if orient == 0:  # horizontal
                # move right
                if y+2 < n and grid[x][y+2] == 0 and grid[x][y+1] == 0:
                    nxt = (x, y+1, 0)
                    if nxt not in visited:
                        visited.add(nxt)
                        queue.append((x, y+1, 0, moves+1))
                # move down
                if x+1 < n and grid[x+1][y] == 0 and grid[x+1][y+1] == 0:
                    nxt = (x+1, y, 0)
                    if nxt not in visited:
                        visited.add(nxt)
                        queue.append((x+1, y, 0, moves+1))
                    # rotate clockwise to vertical
                    nxt_rot = (x, y, 1)
                    if nxt_rot not in visited:
                        visited.add(nxt_rot)
                        queue.append((x, y, 1, moves+1))
            else:  # vertical
                # move down
                if x+2 < n and grid[x+2][y] == 0 and grid[x+1][y] == 0:
                    nxt = (x+1, y, 1)
                    if nxt not in visited:
                        visited.add(nxt)
                        queue.append((x+1, y, 1, moves+1))
                # move right
                if y+1 < n and grid[x][y+1] == 0 and grid[x+1][y+1] == 0:
                    nxt = (x, y+1, 1)
                    if nxt not in visited:
                        visited.add(nxt)
                        queue.append((x, y+1, 1, moves+1))
                    # rotate counterclockwise to horizontal
                    nxt_rot = (x, y, 0)
                    if nxt_rot not in visited:
                        visited.add(nxt_rot)
                        queue.append((x, y, 0, moves+1))
        return -1
      
#include <vector>
#include <queue>
#include <tuple>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<tuple<int,int,int,int>> q; // x, y, orientation, moves
        set<tuple<int,int,int>> visited;
        q.emplace(0, 0, 0, 0);
        visited.emplace(0, 0, 0);
        while (!q.empty()) {
            auto [x, y, orient, moves] = q.front(); q.pop();
            if (x == n-1 && y == n-2 && orient == 0) return moves;
            if (orient == 0) { // horizontal
                // move right
                if (y+2 < n && grid[x][y+2] == 0 && grid[x][y+1] == 0) {
                    auto nxt = make_tuple(x, y+1, 0);
                    if (!visited.count(nxt)) {
                        visited.insert(nxt);
                        q.emplace(x, y+1, 0, moves+1);
                    }
                }
                // move down
                if (x+1 < n && grid[x+1][y] == 0 && grid[x+1][y+1] == 0) {
                    auto nxt = make_tuple(x+1, y, 0);
                    if (!visited.count(nxt)) {
                        visited.insert(nxt);
                        q.emplace(x+1, y, 0, moves+1);
                    }
                    // rotate clockwise
                    auto nxt_rot = make_tuple(x, y, 1);
                    if (!visited.count(nxt_rot)) {
                        visited.insert(nxt_rot);
                        q.emplace(x, y, 1, moves+1);
                    }
                }
            } else { // vertical
                // move down
                if (x+2 < n && grid[x+2][y] == 0 && grid[x+1][y] == 0) {
                    auto nxt = make_tuple(x+1, y, 1);
                    if (!visited.count(nxt)) {
                        visited.insert(nxt);
                        q.emplace(x+1, y, 1, moves+1);
                    }
                }
                // move right
                if (y+1 < n && grid[x][y+1] == 0 && grid[x+1][y+1] == 0) {
                    auto nxt = make_tuple(x, y+1, 1);
                    if (!visited.count(nxt)) {
                        visited.insert(nxt);
                        q.emplace(x, y+1, 1, moves+1);
                    }
                    // rotate counterclockwise
                    auto nxt_rot = make_tuple(x, y, 0);
                    if (!visited.count(nxt_rot)) {
                        visited.insert(nxt_rot);
                        q.emplace(x, y, 0, moves+1);
                    }
                }
            }
        }
        return -1;
    }
};
      
import java.util.*;

class Solution {
    public int minimumMoves(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        // state: x, y, orientation, moves
        queue.offer(new int[]{0, 0, 0, 0});
        visited.add("0,0,0");
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], orient = cur[2], moves = cur[3];
            if (x == n-1 && y == n-2 && orient == 0) return moves;
            if (orient == 0) { // horizontal
                // move right
                if (y+2 < n && grid[x][y+2] == 0 && grid[x][y+1] == 0) {
                    String nxt = (x)+","+(y+1)+",0";
                    if (!visited.contains(nxt)) {
                        visited.add(nxt);
                        queue.offer(new int[]{x, y+1, 0, moves+1});
                    }
                }
                // move down
                if (x+1 < n && grid[x+1][y] == 0 && grid[x+1][y+1] == 0) {
                    String nxt = (x+1)+","+y+",0";
                    if (!visited.contains(nxt)) {
                        visited.add(nxt);
                        queue.offer(new int[]{x+1, y, 0, moves+1});
                    }
                    // rotate clockwise
                    String nxt_rot = x+","+y+",1";
                    if (!visited.contains(nxt_rot)) {
                        visited.add(nxt_rot);
                        queue.offer(new int[]{x, y, 1, moves+1});
                    }
                }
            } else { // vertical
                // move down
                if (x+2 < n && grid[x+2][y] == 0 && grid[x+1][y] == 0) {
                    String nxt = (x+1)+","+y+",1";
                    if (!visited.contains(nxt)) {
                        visited.add(nxt);
                        queue.offer(new int[]{x+1, y, 1, moves+1});
                    }
                }
                // move right
                if (y+1 < n && grid[x][y+1] == 0 && grid[x+1][y+1] == 0) {
                    String nxt = x+","+(y+1)+",1";
                    if (!visited.contains(nxt)) {
                        visited.add(nxt);
                        queue.offer(new int[]{x, y+1, 1, moves+1});
                    }
                    // rotate counterclockwise
                    String nxt_rot = x+","+y+",0";
                    if (!visited.contains(nxt_rot)) {
                        visited.add(nxt_rot);
                        queue.offer(new int[]{x, y, 0, moves+1});
                    }
                }
            }
        }
        return -1;
    }
}
      
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumMoves = function(grid) {
    const n = grid.length;
    // [x, y, orientation, moves]
    let queue = [[0, 0, 0, 0]];
    let visited = new Set();
    visited.add('0,0,0');
    while (queue.length) {
        let [x, y, orient, moves] = queue.shift();
        if (x === n-1 && y === n-2 && orient === 0) return moves;
        if (orient === 0) { // horizontal
            // move right
            if (y+2 < n && grid[x][y+2] === 0 && grid[x][y+1] === 0) {
                let nxt = `${x},${y+1},0`;
                if (!visited.has(nxt)) {
                    visited.add(nxt);
                    queue.push([x, y+1, 0, moves+1]);
                }
            }
            // move down
            if (x+1 < n && grid[x+1][y] === 0 && grid[x+1][y+1] === 0) {
                let nxt = `${x+1},${y},0`;
                if (!visited.has(nxt)) {
                    visited.add(nxt);
                    queue.push([x+1, y, 0, moves+1]);
                }
                // rotate clockwise
                let nxt_rot = `${x},${y},1`;
                if (!visited.has(nxt_rot)) {
                    visited.add(nxt_rot);
                    queue.push([x, y, 1, moves+1]);
                }
            }
        } else { // vertical
            // move down
            if (x+2 < n && grid[x+2][y] === 0 && grid[x+1][y] === 0) {
                let nxt = `${x+1},${y},1`;
                if (!visited.has(nxt)) {
                    visited.add(nxt);
                    queue.push([x+1, y, 1, moves+1]);
                }
            }
            // move right
            if (y+1 < n && grid[x][y+1] === 0 && grid[x+1][y+1] === 0) {
                let nxt = `${x},${y+1},1`;
                if (!visited.has(nxt)) {
                    visited.add(nxt);
                    queue.push([x, y+1, 1, moves+1]);
                }
                // rotate counterclockwise
                let nxt_rot = `${x},${y},0`;
                if (!visited.has(nxt_rot)) {
                    visited.add(nxt_rot);
                    queue.push([x, y, 0, moves+1]);
                }
            }
        }
    }
    return -1;
};

Problem Description

You are given an n x n binary grid representing a board, where 0 represents an empty cell and 1 represents an obstacle. There is a "snake" of length 2 that starts at the top-left corner of the grid, occupying cells (0,0) and (0,1) in a horizontal orientation (tail at (0,0), head at (0,1)). The snake can move by:

  • Moving right (if both cells to the right are empty and within bounds).
  • Moving down (if both cells below are empty and within bounds).
  • Rotating 90 degrees clockwise (if horizontal and the cells below are empty and within bounds).
  • Rotating 90 degrees counterclockwise (if vertical and the cells to the right are empty and within bounds).

The goal is to move the snake to the bottom-right corner in a horizontal orientation, i.e., tail at (n-1, n-2) and head at (n-1, n-1). Return the minimum number of moves required to reach the target position. If it's impossible, return -1.

Constraints:

  • Each move must be valid (no overlapping with obstacles or going out of bounds).
  • You cannot reuse a state (tail position and orientation) that has already been visited.

Thought Process

When first approaching this problem, you might try to simulate every possible move the snake can make, recursively exploring all paths. However, this brute-force method quickly becomes infeasible due to the exponential number of possible positions and orientations, especially as the grid size increases.

Instead, we notice that the problem is about finding the shortest path from the start to the target, where each state is defined by the snake's tail position and orientation. This is similar to classic shortest path problems in graphs, where each valid snake state is a node, and each legal move is an edge.

Therefore, a more efficient approach is to use Breadth-First Search (BFS), which naturally finds the shortest path in an unweighted graph. By tracking visited states (tail position and orientation), we avoid cycles and redundant work.

Solution Approach

Let's break down the algorithm step by step:

  1. Model the State:
    • Each state is represented by (x, y, orientation), where (x, y) is the tail position and orientation is 0 for horizontal and 1 for vertical.
  2. Initialize BFS:
    • Start with the snake at (0, 0, horizontal) and 0 moves.
    • Use a queue to process states in order of increasing moves.
    • Maintain a set of visited states to avoid revisiting.
  3. Process Each State:
    • For each state, consider all possible moves:
      • If horizontal, try moving right, moving down, and rotating clockwise.
      • If vertical, try moving down, moving right, and rotating counterclockwise.
    • For each move, check if the new position is within bounds and all involved cells are empty.
    • If the new state has not been visited, add it to the queue and visited set.
  4. Check for Success:
    • If a state matches the target (tail at (n-1, n-2), horizontal), return the number of moves taken to reach it.
  5. If No Solution:
    • If the queue is exhausted without reaching the target, return -1.

This approach is efficient because:

  • BFS ensures the first time we reach the target, it is via the shortest path.
  • By marking states as visited, we avoid infinite loops and redundant work.

Example Walkthrough

Let's walk through a simple example. Suppose the grid is: 

    0 0 0
    1 1 0
    0 0 0

The snake starts at (0,0, 0,1), horizontal. The goal is to reach (2,1, 2,2), horizontal.

  1. Start: tail at (0,0), horizontal.
  2. Move right: tail at (0,1), horizontal. (head at (0,2))
  3. Move down: tail at (1,1), horizontal. (head at (1,2)). But grid[1][1] == 1, so this is invalid.
  4. From (0,1), horizontal, try moving right: tail at (0,2), but head would be at (0,3) (out of bounds), invalid.
  5. From (0,1), horizontal, try moving down: tail at (1,1), but grid[1][1] == 1, invalid.
  6. From (0,1), horizontal, try rotating: not possible due to obstacle below.
  7. From (0,0), horizontal, try rotating: not possible due to obstacle below.
  8. From (0,0), horizontal, try moving down: tail at (1,0), but grid[1][0] == 1, invalid.
  9. Back to start, try rotating: not possible due to obstacle below.
  10. From (0,1), horizontal, try rotating: not possible due to obstacle below.
  11. From (0,1), horizontal, try moving right: invalid as above.
  12. From (0,1), horizontal, try moving down: invalid as above.
  13. From (0,2), horizontal: not possible (out of bounds).
  14. From (0,1), horizontal, try rotating: not possible.
  15. Now, try from (0,0), horizontal, try moving down: invalid.
  16. Try rotating from (0,0): not possible.
  17. Try moving down from (0,1), horizontal: invalid.
  18. Try moving right from (0,1), horizontal: invalid.
  19. No more moves; thus, return -1.

In this example, it is not possible to reach the target because of the obstacles blocking all valid paths.

In a grid with no obstacles, the snake would proceed right, then down, then possibly rotate to reach the target.

Time and Space Complexity

Brute-force approach:

  • Explores all possible sequences of moves, leading to exponential time complexity: O(3K), where K is the number of steps possible. This is impractical for large grids.
  • Space complexity is also exponential due to the call stack and storage of visited states.
Optimized BFS approach:
  • The number of distinct states is O(n2 * 2), since for each cell, the snake can be in two orientations.
  • Each state is processed at most once, so time complexity is O(n2).
  • Space complexity is also O(n2), to store the queue and visited states.
  • Each state checks a constant (up to 3) possible moves, so the BFS is efficient.

Summary

This problem is a classic application of BFS for shortest path finding, but with the twist of modeling a 2-cell snake with orientation. By representing each state as a combination of tail position and orientation, and using BFS with a visited set, we efficiently explore all valid moves without redundancy. The solution is elegant because it transforms a seemingly complex movement puzzle into a well-understood graph traversal problem.