# Minimum Moves to Reach Target with Rotations
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-reach-target-with-rotations
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Kakao](https://scaleengineer.com/companies/kakao)
---
## Problem
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)`.  
![](https://assets.glich.co/dsa/minimum-moves-to-reach-target-with-rotations/image0.png)
* 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)`.  
![](https://assets.glich.co/dsa/minimum-moves-to-reach-target-with-rotations/image1.png)

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return `-1`.

**Example 1:**

**![](https://assets.glich.co/dsa/minimum-moves-to-reach-target-with-rotations/image2.png)**

**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 <= 100`
* `0 <= grid[i][j] <= 1`
* It is guaranteed that the snake starts at empty cells.

# Approaches
## Depth-First Search (DFS) with Memoization
This approach uses recursion to explore possible paths from the start to the target. A naive DFS is not suitable for finding the shortest path as it might explore a very long path first and is not guaranteed to find the shortest one. To make it work correctly and efficiently, we must use memoization (a form of dynamic programming) to keep track of the minimum number of moves to reach each possible state (a combination of position and orientation). This prevents re-exploring states with a longer path and ensures we find the optimal solution.
**Time:** O(N^2) - The number of states is `2 * N^2`. Each state is processed a constant number of times. The `dfs` function for a state is effectively called only when we find a shorter path to it, leading to an exploration of the state graph similar to Dijkstra's algorithm. · **Space:** O(N^2) - The `dist` array for memoization requires O(N*N*2) space. The recursion stack depth can also go up to O(N^2) in the worst case.
**Pros:** It is a valid state-space search algorithm that can solve the problem correctly with memoization.
**Cons:** Less intuitive for shortest path problems on unweighted graphs compared to BFS.; Recursive implementation can lead to stack overflow on large grids or for problems requiring deep recursion.; Typically has higher constant overhead than an iterative BFS approach due to function call stacks.
### Explanation
The core idea is to treat the problem as finding the shortest path in a state graph. A state is defined by `(row, col, orientation)`. We use a 3D array `dist[n][n][2]` to store the shortest distance (minimum moves) from the start state `(0, 0, 0)` to every other state. This array is initialized with a value representing infinity.

The search starts from the initial state `(0, 0, 0)` with 0 moves. We define a recursive function `dfs(r, c, orientation)` that explores the graph. When visiting a state, it calculates the moves to reach its neighbors (1 more than the current state's moves). If this new path to a neighbor is shorter than any previously recorded path, it updates the neighbor's distance in the `dist` array and makes a recursive call from that neighbor. This ensures that we always explore from the best-known path.

After the initial call `dfs(0, 0, 0)` completes, the `dist` array will be populated with the minimum moves to all reachable states. The final answer is the value at the target state, `dist[n-1][n-2][0]`. If this value remains at infinity, it means the target is unreachable.

```java
class Solution {
    int[][][] dist;
    int n;
    int[][] grid;

    public int minimumMoves(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        this.dist = new int[n][n][2]; // 0: horizontal, 1: vertical
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j][0] = Integer.MAX_VALUE;
                dist[i][j][1] = Integer.MAX_VALUE;
            }
        }
        
        dist[0][0][0] = 0;
        dfs(0, 0, 0);

        int result = dist[n - 1][n - 2][0];
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private void dfs(int r, int c, int orientation) {
        int moves = dist[r][c][orientation];

        if (orientation == 0) { // Horizontal snake at (r, c) and (r, c+1)
            // 1. Move right
            if (c + 2 < n && grid[r][c + 2] == 0) {
                if (moves + 1 < dist[r][c + 1][0]) {
                    dist[r][c + 1][0] = moves + 1;
                    dfs(r, c + 1, 0);
                }
            }
            // 2. Move down & 3. Rotate clockwise
            if (r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0) {
                // Move down
                if (moves + 1 < dist[r + 1][c][0]) {
                    dist[r + 1][c][0] = moves + 1;
                    dfs(r + 1, c, 0);
                }
                // Rotate clockwise
                if (moves + 1 < dist[r][c][1]) {
                    dist[r][c][1] = moves + 1;
                    dfs(r, c, 1);
                }
            }
        } else { // Vertical snake at (r, c) and (r+1, c)
            // 1. Move down
            if (r + 2 < n && grid[r + 2][c] == 0) {
                if (moves + 1 < dist[r + 1][c][1]) {
                    dist[r + 1][c][1] = moves + 1;
                    dfs(r + 1, c, 1);
                }
            }
            // 2. Move right & 3. Rotate counter-clockwise
            if (c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0) {
                // Move right
                if (moves + 1 < dist[r][c + 1][1]) {
                    dist[r][c + 1][1] = moves + 1;
                    dfs(r, c + 1, 1);
                }
                // Rotate counter-clockwise
                if (moves + 1 < dist[r][c][0]) {
                    dist[r][c][0] = moves + 1;
                    dfs(r, c, 0);
                }
            }
        }
    }
}
```
### Algorithm
- We define a state by the snake's top-left coordinate `(r, c)` and its orientation (0 for horizontal, 1 for vertical).
- We use a 3D array, `dist[n][n][2]`, to store the minimum moves to reach each state, initialized to infinity. This acts as our memoization table.
- A recursive function, `dfs(r, c, orientation)`, is the core of this approach.
- The function explores all valid next moves from the current state `(r, c, orientation)`.
- For each neighbor, if a shorter path is found (i.e., `current_moves + 1 < dist[neighbor]`), we update the neighbor's distance in the `dist` array and recursively call `dfs` on that neighbor.
- This process is similar to a recursive implementation of Dijkstra's algorithm. The pruning happens by not recursing if a path is not shorter than one already found.
- The initial call is made after setting the distance to the start state `dist[0][0][0]` to 0.
- After the recursion completes, the answer is the value stored in `dist[n-1][n-2][0]`. If the value is still infinity, the target is unreachable.

## Breadth-First Search (BFS)
Breadth-First Search (BFS) is the ideal and most efficient algorithm for finding the shortest path in an unweighted graph, which is exactly what this problem represents. The 'nodes' of our graph are the possible states of the snake (position and orientation), and the 'edges' are the valid moves, each with a weight of 1. BFS systematically explores the graph layer by layer, where each layer corresponds to an increase in the number of moves. This guarantees that the first time we reach the target state, it will be via a path with the minimum possible number of moves.
**Time:** O(N^2) - The number of states is `2 * N^2`. Each state is enqueued and dequeued at most once. The work done for each state (checking neighbors) is constant. · **Space:** O(N^2) - The `visited` array requires O(N*N*2) space. The queue, in the worst case, can hold a number of states proportional to N^2.
**Pros:** Guaranteed to find the shortest path in terms of number of moves.; Conceptually straightforward and the standard algorithm for unweighted shortest path problems.; Iterative nature avoids stack depth limitations that can affect recursive solutions.
**Cons:** Performs a blind search, potentially exploring many states that are not on a path towards the goal. In some cases, an informed search like A* could be faster.
### Explanation
We use a queue to manage the states to visit. Each element in the queue will represent a state, for example, an array `[row, col, orientation]`. To avoid cycles and redundant computations, we use a 3D boolean array `visited[n][n][2]` to keep track of states that have already been added to the queue.

The search starts by adding the initial state `[0, 0, 0]` (horizontal at `(0,0)`) to the queue and marking it as visited. The algorithm then proceeds in levels, controlled by a loop that processes all items in the queue for a given move count. In each level, we dequeue all states, generate their valid neighbors (right, down, rotate), and for any neighbor that hasn't been visited, we mark it as visited and add it to the queue. After processing all states at a level, we increment our `moves` counter. If we dequeue the target state `[n-1, n-2, 0]`, we can immediately return the current `moves` count as the shortest path has been found. If the queue becomes empty before the target is found, no path exists.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int minimumMoves(int[][] grid) {
        int n = grid.length;
        // state: [row, col, orientation], 0 for horizontal, 1 for vertical
        Queue<int[]> queue = new LinkedList<>();
        boolean[][][] visited = new boolean[n][n][2];

        // Initial state
        queue.offer(new int[]{0, 0, 0});
        visited[0][0][0] = true;
        
        int moves = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int r = current[0];
                int c = current[1];
                int orientation = current[2];

                // Target reached
                if (r == n - 1 && c == n - 2 && orientation == 0) {
                    return moves;
                }

                // Explore next states
                if (orientation == 0) { // Horizontal
                    // 1. Move right
                    if (c + 2 < n && grid[r][c + 2] == 0 && !visited[r][c + 1][0]) {
                        visited[r][c + 1][0] = true;
                        queue.offer(new int[]{r, c + 1, 0});
                    }
                    // 2. Move down and 3. Rotate clockwise
                    if (r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0) {
                        // Move down
                        if (!visited[r + 1][c][0]) {
                            visited[r + 1][c][0] = true;
                            queue.offer(new int[]{r + 1, c, 0});
                        }
                        // Rotate clockwise
                        if (!visited[r][c][1]) {
                            visited[r][c][1] = true;
                            queue.offer(new int[]{r, c, 1});
                        }
                    }
                } else { // Vertical
                    // 1. Move down
                    if (r + 2 < n && grid[r + 2][c] == 0 && !visited[r + 1][c][1]) {
                        visited[r + 1][c][1] = true;
                        queue.offer(new int[]{r + 1, c, 1});
                    }
                    // 2. Move right and 3. Rotate counter-clockwise
                    if (c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0) {
                        // Move right
                        if (!visited[r][c + 1][1]) {
                            visited[r][c + 1][1] = true;
                            queue.offer(new int[]{r, c + 1, 1});
                        }
                        // Rotate counter-clockwise
                        if (!visited[r][c][0]) {
                            visited[r][c][0] = true;
                            queue.offer(new int[]{r, c, 0});
                        }
                    }
                }
            }
            moves++;
        }

        return -1; // Target not reachable
    }
}
```
### Algorithm
- Define a state by `(r, c, orientation)`, where `(r, c)` is the top-left cell and `orientation` is 0 for horizontal, 1 for vertical.
- Initialize a queue and add the starting state `(0, 0, 0)`.
- Initialize a 3D boolean array `visited[n][n][2]` and mark the starting state as visited to avoid cycles.
- Initialize `moves = 0`.
- While the queue is not empty:
  - Get the number of states at the current level (`size = queue.size()`).
  - Loop `size` times to process all states at the current level.
    - Dequeue a state `(r, c, orientation)`.
    - If it's the target state `(n-1, n-2, 0)`, return `moves`.
    - Generate all valid next states (move right, move down, rotate).
    - For each valid next state `(nr, nc, no)` that has not been visited:
      - Mark it as visited: `visited[nr][nc][no] = true`.
      - Enqueue the new state `(nr, nc, no)`.
  - Increment `moves`.
- If the loop finishes (queue becomes empty), it means the target is unreachable, so return -1.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int[][] grid;
private
  boolean[][] vis;
private
  Deque<int[]> q = new ArrayDeque<>();
public
  int minimumMoves(int[][] grid) {
    this.grid = grid;
    n = grid.length;
    vis = new boolean[n * n][2];
    int[] target = {n * n - 2, n * n - 1};
    q.offer(new int[]{0, 1});
    vis[0][0] = true;
    int ans = 0;
    while (!q.isEmpty()) {
      for (int k = q.size(); k > 0; --k) {
        var p = q.poll();
        if (p[0] == target[0] && p[1] == target[1]) {
          return ans;
        }
        int i1 = p[0] / n, j1 = p[0] % n;
        int i2 = p[1] / n, j2 = p[1] % n;
```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var minimumMoves = function ( grid ) { const n = grid . length ; const target = [ n * n - 2 , n * n - 1 ]; const q = [[ 0 , 1 ]]; const vis = Array . from ({ length : n * n }, () => Array ( 2 ). fill ( false )); vis [ 0 ][ 0 ] = true ; const move = ( i1 , j1 , i2 , j2 ) => { if ( i1 >= 0 && i1 < n && j1 >= 0 && j1 < n && i2 >= 0 && i2 < n && j2 >= 0 && j2 < n ) { const a = i1 * n + j1 ; const b = i2 * n + j2 ; const status = i1 === i2 ? 0 : 1 ; if ( ! vis [ a ][ status ] && grid [ i1 ][ j1 ] == 0 && grid [ i2 ][ j2 ] == 0 ) { q . push ([ a , b ]); vis [ a ][ status ] = true ; } } }; let ans = 0 ; while ( q . length ) { for ( let k = q . length ; k ; -- k ) { const p = q . shift (); if ( p [ 0 ] === target [ 0 ] && p [ 1 ] === target [ 1 ]) { return ans ; } const [ i1 , j1 ] = [ ~~ ( p [ 0 ] / n ), p [ 0 ] % n ]; const [ i2 , j2 ] = [ ~~ ( p [ 1 ] / n ), p [ 1 ] % n ]; 
```

### CPP

```cpp
class Solution {
public:
  int minimumMoves(vector<vector<int>> &grid) {
    int n = grid.size();
    auto target = make_pair(n * n - 2, n * n - 1);
    queue<pair<int, int>> q;
    q.emplace(0, 1);
    bool vis[n * n][2];
    memset(vis, 0, sizeof vis);
    vis[0][0] = true;
    auto move = [&](int i1, int j1, int i2, int j2) {
      if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n && i2 >= 0 && i2 < n &&
          j2 >= 0 && j2 < n) {
        int a = i1 * n + j1, b = i2 * n + j2;
        int status = i1 == i2 ? 0 : 1;
        if (!vis[a][status] && grid[i1][j1] == 0 && grid[i2][j2] == 0) {
          q.emplace(a, b);
          vis[a][status] = true;
        }
      }
    };
    int ans = 0;
    while (!q.empty()) {
      for (int k = q.size(); k; --k) {
        auto p = q.front();
        q.pop();
        if (p == target) {
          return ans;
        }
        auto [a, b] = p;
        int i1 = a / n, j1 = a % n;
        int i2 = b / n, j2 = b % n;
```

### Python

```python
class Solution:
    # 尝试向右平移（保持身体水平/垂直状态） move ( i1 , j1 + 1 , i2 , j2 + 1 ) # 尝试向下平移（保持身体水平/垂直状态） move ( i1 + 1 , j1 , i2 + 1 , j2 ) # 当前处于水平状态，且 grid[i1 + 1][j2] 无障碍，尝试顺时针旋转90° if i1 == i2 and i1 + 1 < n and grid [ i1 + 1 ][ j2 ] == 0 : move ( i1 , j1 , i1 + 1 , j1 ) # 当前处于垂直状态，且 grid[i2][j1 + 1] 无障碍，尝试逆时针旋转90° if j1 == j2 and j1 + 1 < n and grid [ i2 ][ j1 + 1 ] == 0 : move ( i1 , j1 , i1 , j1 + 1 ) ans += 1 return - 1
    def minimumMoves(self, grid: List[List[int]]) -> int: def move(i1, j1, i2, j2): if 0 <= i1 < n and 0 <= j1 < n and 0 <= i2 < n and 0 <= j2 < n: a, b = i1 * n + j1, i2 * n + j2 status = 0 if i1 == i2 else 1 if (a, status) not in vis and grid[i1][j1] == 0 and grid[i2][j2] == 0: q . append((a, b)) vis . add((a, status)) n = len(grid) target = (n * n - 2, n * n - 1) q = deque([(0, 1)]) vis = {(0, 0)} ans = 0 while q: for _ in range(len(q)): a, b = q . popleft() if (a, b) == target: return ans i1, j1 = a // n, a % n i2, j2 = b // n, b % n

```