1210. Minimum Moves to Reach Target with Rotations

HardBreadth-First SearchArrayMatrix
Leetcode Link

Problem Description

In this problem, we are tasked with determining the minimum number of moves required for a snake to reach the bottom-right corner of an n by n grid. The snake occupies two cells at the beginning, starting from the top left corner. The cells in the grid can be empty (denoted by 0) or blocked (denoted by 1). The objective is to move the snake from its starting position to occupy the two cells at the bottom right corner, using only the following moves:

  • Move one cell to the right (if it's not blocked).
  • Move one cell down (if it's not blocked).
  • Rotate clockwise if the snake is horizontal and the cells beneath are empty.
  • Rotate counterclockwise if the snake is vertical and the cells to its right are empty.

The goal is to do this in as few moves as possible, or determine that it's not possible by returning -1 if there is no way for the snake to reach the target.

Intuition

To solve this problem, we use Breadth-First Search (BFS) to explore the grid. BFS is an ideal strategy for this situation because it explores all possible moves at each depth level before going deeper, ensuring that the shortest path is found if one exists.

Here’s a step-by-step breakdown of how we can implement BFS in this scenario:

  1. Represent the snake's position as a pair of coordinates each for its head and tail. Additionally, maintain a record of the snake's orientation (horizontal or vertical).
  2. Start with the snake in the starting position and orientation in a queue.
  3. Mark the starting position and orientation as visited to avoid revisiting.
  4. Use the queue to explore all possible moves from the current position, including moving right, moving down, and rotations, if applicable, based on the snake's orientation and the availability of empty cells.
  5. For each valid move, check if the snake's new position has been visited before. If it hasn't, add this new position and orientation to the queue and mark it as visited.
  6. If while exploring we reach the target position, that means we have found the shortest path, and we can return the number of moves taken to reach there.
  7. Continue exploring until the queue is empty.
  8. If the queue gets empty and the target has not been reached, this means that there is no possible way to reach the target, so we return -1.

The BFS ensures that once the snake reaches the target, it has done so using the minimum number of moves because all paths shorter than the current would have already been explored.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The solution follows the Breadth-First Search (BFS) strategy using a queue to keep track of all possible positions and orientations the snake can take as it moves or rotates.

Here's how the implementation unfolds:

  • A two-dimensional list grid represents the playing field with 0s for empty cells and 1s for blocked cells.

  • The target position is the two cells at bottom-right corner (n-1, n-2) and (n-1, n-1).

  • A deque is used as a queue q to perform BFS, initialized with the starting position of the snake.

  • A set named vis is used to keep track of visited states to avoid processing a state more than once. A state comprises the linearized positions of the head (i1, j1) and tail (i2, j2) of the snake, alongside its orientation (horizontal 0 or vertical 1).

    Linearization: Since the grid can be represented as a 2D array, for convenience the 2D coordinates are linearized into 1D using the formula i*n + j, where n is the length of one side of the grid.

  • We define a helper function move() to check whether the next move is within the grid, and if the positions after the move are not visited and not blocked.

  • The BFS loop begins, and for each iteration, we pop elements from the queue, one for each move.

  • For each position popped from the queue, we:

    1. Check if this is the target position. If the target is reached, return the number of moves taken, which is ans.
    2. Try to move right if the snake is horizontal.
    3. Try to move down if the snake is vertical.
    4. Perform a clockwise rotation if the snake is horizontal and the cells below are empty.
    5. Perform a counterclockwise rotation if the snake is vertical and the cells to the right are empty.

  • After exploring all possible moves from the current state, we increment the ans denoting the number of moves.

  • If we finish processing every possible state the snake can be in and haven't reached the target, then the target is not reachable, so we return -1.

Key points in this approach:

  • Since we are using BFS, the first time we reach the target, we ensure it's the minimum number of moves as BFS explores each level breadth-wise before moving on to deeper levels.
  • Maintaining a visited set is crucial to the performance of the solution as it prevents re-exploring the same states.

The algorithm complexity is O(n^2) considering the n*n grid, as every cell can be visited once for each orientation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Suppose we have a 3x3 grid where the snake starts at the top left and we want to reach the bottom right corner. Our grid looks like this:

10 (snake head)
20 (snake tail)
30
40 0 0
50 0 0
60 0 0

Here are the steps illustrating how the BFS solution is applied in our example:

  1. Initialize the queue q with the starting position of the snake. The head is at (0, 0) and the tail is at (0, 1), which is horizontal. This is represented as ((0, 0), (0, 1), 0) in our queue where 0 indicates a horizontal orientation.

  2. Initialize the vis set with the same values to mark the initial state as visited.

  3. Pop this state from the queue and explore all possible moves:

    • We can move right, resulting in a new state ((0, 1), (0, 2), 0) if not blocked or already visited.
    • We cannot move down as the snake is horizontal.
    • We cannot rotate as we are at the top edge.

  4. Add the right move state to the queue.

  5. The new state after moving right is popped from the queue for exploration:

    • We can rotate clockwise since the snake is horizontal and the cells below (1, 1) and (1, 2) are empty. This creates a new state of the snake being vertical at ((0, 2), (1, 2), 1).

  6. Add this rotated state to the queue.

  7. Pop the rotated state for exploration:

    • Now the snake head is at (0, 2) and the tail is at (1, 2), and we can move down since it's vertical, resulting in a head at (1, 2) and a tail at (2, 2), now being horizontal ((1, 2), (2, 2), 0).

  8. Add this down move state to the queue.

  9. Continue this process until we either:

    • Reach the end of the queue without the snake occupying both bottom-right cells, in which case we return -1.
    • Successfully reach the bottom-right corner with the snake's head at (2, 1) and tail at (2, 2), in which case we return the number of moves, ans.

In this simple example, the snake can indeed reach the bottom-right corner in a few moves by following the described steps. The actual output in this example would be the number of moves taken to reach the target position using BFS.

The important takeaway from this approach is the systematic exploration of all moves from each state without revisiting any state, ensuring efficiency and the guarantee that once the target is reached, it is done in the minimum number of moves.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def minimumMoves(self, grid) -> int:
5        # Helper function to evaluate and add new moves to the queue
6        def move(start_row, start_col, end_row, end_col):
7            # Check if the move is inside the bounds of the grid
8            if 0 <= start_row < grid_size and 0 <= start_col < grid_size and \
9               0 <= end_row < grid_size and 0 <= end_col < grid_size:
10                # Convert the coordinates to a linear representation
11                start_pos = start_row * grid_size + start_col
12                end_pos = end_row * grid_size + end_col
13                # 0 for horizontal, 1 for vertical based on the start and end row comparison
14                status = 0 if start_row == end_row else 1
15                # Check if the move is valid and not visited, and the grid cells are empty (0)
16                if (start_pos, status) not in visited and grid[start_row][start_col] == 0 and grid[end_row][end_col] == 0:
17                    # Add the valid move to the queue for further exploration
18                    queue.append((start_pos, end_pos))
19                    # Mark this state as visited
20                    visited.add((start_pos, status))
21
22        # Initial grid size
23        grid_size = len(grid)
24        # Create a target state which represents the tail end of the snake
25        target = (grid_size * grid_size - 2, grid_size * grid_size - 1)
26        # Initialize a queue with the starting position of the snake
27        queue = deque([(0, 1)]) # Snake starts horizontally from the top left corner
28        # Set to keep track of visited positions and orientations
29        visited = {(0, 0)}
30        # Move counter
31        moves_count = 0
32      
33        # BFS Loop
34        while queue:
35            # Explore the nodes at the current level
36            for _ in range(len(queue)):
37                start_pos, end_pos = queue.popleft()
38                # Check if the current state is the target state
39                if (start_pos, end_pos) == target:
40                    return moves_count
41                # Calculate row and column from linear positions
42                start_row, start_col = divmod(start_pos, grid_size)
43                end_row, end_col = divmod(end_pos, grid_size)
44              
45                # Try to move right if within bounds
46                move(start_row, start_col + 1, end_row, end_col + 1)
47                # Try to move down if within bounds
48                move(start_row + 1, start_col, end_row + 1, end_col)
49                # Try to rotate clockwise if there's space and the snake is horizontal
50                if start_row == end_row and start_row + 1 < grid_size and grid[start_row + 1][end_col] == 0:
51                    move(start_row, start_col, start_row + 1, start_col)
52                # Try to rotate counterclockwise if there's space and the snake is vertical
53                if start_col == end_col and start_col + 1 < grid_size and grid[end_row][start_col + 1] == 0:
54                    move(start_row, start_col, start_row, start_col + 1)
55          
56            # Increment the moves counter after all moves at the current level have been processed
57            moves_count += 1
58      
59        # Return -1 if reaching the target is not possible
60        return -1
61
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4class Solution {
5    // Class variables
6    private int size; // Size of the grid
7    private int[][] grid; // The given grid
8    private boolean[][] visited; // Visited state for each cell and orientation 
9    private Deque<int[]> queue = new ArrayDeque<>(); // Queue for conducting BFS
10
11    public int minimumMoves(int[][] grid) {
12        this.grid = grid;
13        size = grid.length;
14        visited = new boolean[size * size][2]; // 2 for the two possible orientations
15        int[] target = {size * size - 2, size * size - 1}; // The target state
16        queue.offer(new int[] {0, 1}); // Starting state (head at 0 and tail at 1)
17        visited[0][0] = true; // Set the starting state as visited with a horizontal orientation
18      
19        int steps = 0; // Number of steps to reach the target
20        // BFS to find the minimum moves required
21        while (!queue.isEmpty()) {
22            int currentLevelSize = queue.size();
23            for (int i = 0; i < currentLevelSize; ++i) {
24                int[] position = queue.poll(); // Get the current position
25
26                // If the current position is the target, return the steps count
27                if (position[0] == target[0] && position[1] == target[1]) {
28                    return steps;
29                }
30
31                // Calculate coordinates from serialized positions
32                int headRow = position[0] / size, headCol = position[0] % size;
33                int tailRow = position[1] / size, tailCol = position[1] % size;
34
35                // Try moving right and down for both head and tail
36                moveIfPossible(headRow, headCol + 1, tailRow, tailCol + 1);
37                moveIfPossible(headRow + 1, headCol, tailRow + 1, tailCol);
38
39                // Rotate clockwise if there is space and snake is horizontal
40                if (headRow == tailRow && headRow + 1 < size && grid[headRow + 1][tailCol] == 0) {
41                    moveIfPossible(headRow, headCol, headRow + 1, headCol);
42                }
43                // Rotate counter-clockwise if there is space and snake is vertical
44                if (headCol == tailCol && headCol + 1 < size && grid[tailRow][headCol + 1] == 0) {
45                    moveIfPossible(headRow, headCol, headRow, headCol + 1);
46                }
47            }
48            steps++; // Increment the step count after processing all positions at the current level
49        }
50      
51        return -1; // If the target is not reachable return -1
52    }
53
54    // Function to attempt a move if possible
55    private void moveIfPossible(int headRow, int headCol, int tailRow, int tailCol) {
56        // Check if both the new head and tail are within the grid bounds
57        if (headRow >= 0 && headRow < size && headCol >= 0 && headCol < size
58            && tailRow >= 0 && tailRow < size && tailCol >= 0 && tailCol < size) {
59            int headPos = headRow * size + headCol;
60            int tailPos = tailRow * size + tailCol;
61            int orientation = headRow == tailRow ? 0 : 1; // Horizontal is 0, Vertical is 1
62          
63            // If the move is not visited and does not hit an obstacle
64            if (!visited[headPos][orientation] && grid[headRow][headCol] == 0 && grid[tailRow][tailCol] == 0) {
65                queue.offer(new int[] {headPos, tailPos}); // Enqueue the new move
66                visited[headPos][orientation] = true; // Mark this move as visited
67            }
68        }
69    }
70}
71
1#include <vector>
2#include <queue>
3#include <cstring>
4
5class Solution {
6public:
7    int minimumMoves(vector<vector<int>>& grid) {
8        int gridSize = grid.size(); // Obtain the size of the grid.
9        pair<int, int> target = make_pair(gridSize * gridSize - 2, gridSize * gridSize - 1); // Pair representing the target state.
10        queue<pair<int, int>> moveQueue; // Queue to manage BFS.
11        moveQueue.emplace(0, 1); // Start state with the snake's head at 0 and tail at 1.
12      
13        bool visited[gridSize * gridSize][2]; // 2D array to check if a state [cell][orientation] has been visited.
14        memset(visited, 0, sizeof visited); // Initialize the visited array with 0.
15        visited[0][0] = true; // Mark the start state as visited.
16
17        // Lambda function to attempt a move and add to queue if valid.
18        auto attemptMove = [&](int headRow, int headCol, int tailRow, int tailCol) {
19            if (headRow >= 0 && headRow < gridSize && headCol >= 0 && headCol < gridSize
20                && tailRow >= 0 && tailRow < gridSize && tailCol >= 0 && tailCol < gridSize) {
21                int headIdx = headRow * gridSize + headCol; // Flatten 2D to 1D index for the head.
22                int tailIdx = tailRow * gridSize + tailCol; // Flatten 2D to 1D index for the tail.
23                int orientation = (headRow == tailRow) ? 0 : 1; // Orientation of the snake: 0 for horizontal, 1 for vertical.
24                if (!visited[headIdx][orientation] && grid[headRow][headCol] == 0 && grid[tailRow][tailCol] == 0) {
25                    moveQueue.emplace(headIdx, tailIdx);
26                    visited[headIdx][orientation] = true;
27                }
28            }
29        };
30
31        int numOfMoves = 0; // Counter for the number of moves.
32        while (!moveQueue.empty()) {
33            int queueSize = moveQueue.size();
34            for (int k = queueSize; k > 0; --k) {
35                pair<int, int> currentPos = moveQueue.front();
36                moveQueue.pop();
37                if (currentPos == target) { // Check if we reached the target state.
38                    return numOfMoves;
39                }
40              
41                int headIdx = currentPos.first;
42                int tailIdx = currentPos.second;
43                int headRow = headIdx / gridSize;
44                int headCol = headIdx % gridSize;
45                int tailRow = tailIdx / gridSize;
46                int tailCol = tailIdx % gridSize;
47              
48                // Attempt to move right.
49                attemptMove(headRow, headCol + 1, tailRow, tailCol + 1);
50                // Attempt to move down.
51                attemptMove(headRow + 1, headCol, tailRow + 1, tailCol);
52                // Attempt to rotate clockwise from horizontal to vertical, if space is available.
53                if (headRow == tailRow && headRow + 1 < gridSize && grid[headRow + 1][tailCol] == 0) {
54                    attemptMove(headRow, headCol, headRow + 1, headCol);
55                }
56                // Attempt to rotate counterclockwise from vertical to horizontal, if space is available.
57                if (headCol == tailCol && headCol + 1 < gridSize && grid[tailRow][headCol + 1] == 0) {
58                    attemptMove(headRow, headCol, headRow, headCol + 1);
59                }
60            }
61            numOfMoves++; // Increment the number of moves after processing all current moves.
62        }
63        return -1; // If the loop ends without reaching the target, return -1 to indicate it's impossible to reach the target.
64    }
65};
66
1function minimumMoves(grid: number[][]): number {
2    const gridSize = grid.length;
3    const targetPosition: number[] = [gridSize * gridSize - 2, gridSize * gridSize - 1];
4    const queue: number[][] = [[0, 1]]; // Queue for BFS with initial snake position
5    const visited = Array.from({ length: gridSize * gridSize }, () => Array(2).fill(false));
6    visited[0][0] = true; // Mark the start position as visited
7
8    // Helper function to attempt a move and add it to the queue if valid and unvisited
9    const attemptMove = (row1: number, col1: number, row2: number, col2: number) => {
10        if (row1 >= 0 && row1 < gridSize && col1 >= 0 && col1 < gridSize &&
11            row2 >= 0 && row2 < gridSize && col2 >= 0 && col2 < gridSize) {
12                const index1 = row1 * gridSize + col1;
13                const index2 = row2 * gridSize + col2;
14                const orientation = row1 === row2 ? 0 : 1; // Horizontal if 0, vertical if 1
15                if (!visited[index1][orientation] && grid[row1][col1] == 0 && grid[row2][col2] == 0) {
16                    queue.push([index1, index2]);
17                    visited[index1][orientation] = true;
18                }
19        }
20    };
21
22    // BFS to find the minimum moves
23    let moves = 0;
24    while (queue.length) {
25        for (let size = queue.length; size; --size) {
26            const currentPosition = queue.shift();
27            if (currentPosition[0] === targetPosition[0] && currentPosition[1] === targetPosition[1]) {
28                return moves; // Reached the target
29            }
30            const [row1, col1] = [~~(currentPosition[0] / gridSize), currentPosition[0] % gridSize];
31            const [row2, col2] = [~~(currentPosition[1] / gridSize), currentPosition[1] % gridSize];
32          
33            // Attempt moves in all possible directions
34            attemptMove(row1, col1 + 1, row2, col2 + 1);
35            attemptMove(row1 + 1, col1, row2 + 1, col2);
36          
37            // Attempt rotations if there's space and if the snake is aligned
38            if (row1 === row2 && row1 + 1 < gridSize && grid[row1 + 1][col2] === 0) {
39                attemptMove(row1, col1, row1 + 1, col1);
40            }
41            if (col1 === col2 && col1 + 1 < gridSize && grid[row2][col1 + 1] === 0) {
42                attemptMove(row1, col1, row1, col1 + 1);
43            }
44        }
45        // Increment the moves after each layer of BFS
46        ++moves;
47    }
48
49    // If the target cannot be reached, return -1
50    return -1;
51}
52
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used in a depth first search?

Time and Space Complexity

The given code is a breadth-first search (BFS) algorithm that operates on a grid to find the minimum number of moves to get from the starting position to the target position. The code takes into account the snake's orientation (either horizontal or vertical) within the grid.

Time Complexity:

The time complexity of the BFS approach to traversing the grid can be analyzed as follows:

  • The queue q can contain at most 2 * n * n possible positions for all combinations of (i1, j1, i2, j2) given the snake occupies two cells at each step and there are n * n cells in the grid.
  • For each position, we attempt up to 4 moves: right, down, clockwise rotation, and counter-clockwise rotation.
  • Therefore, in the worst case, each element will be inserted and removed from the queue once, leading to an operation count for each of the 2 * n * n positions.
  • As such, the computational complexity of the BFS exploration is O(4 * 2 * n^2), which simplifies to O(n^2).

Space Complexity:

The space complexity can be evaluated by considering the storage requirements:

  • The queue q can grow up to 2 * n * n elements storing distinct positions of the snake on the grid.
  • The vis set also stores unique states, which may have at most 2 * n * n entries.
  • There is a constant overhead for local variables and the BFS queue's inherent elements; however, this does not affect the overall degree of the polynomial space requirement.
  • This leads to a space complexity of O(2 * n^2), which simplifies to O(n^2).

Overall, the time complexity of the algorithm is O(n^2), and the space complexity is also O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫