864. Shortest Path to Get All Keys

HardBit ManipulationBreadth-First SearchArrayMatrix
Leetcode Link

Problem Description

In this problem, you are asked to find the shortest path to acquire all keys in a given grid. The grid representation is as follows:

  • A '.' character represents an empty cell where you can walk.
  • A '#' character represents a wall that you cannot pass through.
  • An '@' character represents your starting point.
  • Lowercase letters ('a' to 'f') represent keys.
  • Uppercase letters ('A' to 'F') correspond to locks.

You are able to move one space at a time in one of the four cardinal directions (up, down, left, or right). You cannot exit the boundaries of the grid, and you cannot pass through walls. If you encounter a key, you can pick it up. You can only pass through a lock if you've already picked up the corresponding key. The keys and locks use the first k letters of the English alphabet, and there is exactly one key for each lock, and one lock for each key.

The task is to return the minimum number of moves required to pick up all keys. If it is not possible to obtain all the keys, the function should return -1.

Intuition

The intuition behind the solution is to perform a breadth-first search (BFS) to explore the grid systematically. In a BFS, you visit each accessible cell in the grid by starting from your initial position and moving in all four cardinal directions. As you move, you'll track certain key aspects:

  • The current position (i, j) on the grid.
  • The set of keys you have collected so far (represented as a bit mask state).

The bit mask for the state allows tracking which keys have been picked up without needing a separate list or structure. By using bitwise operations, we convert the collection of keys to an integer, where the bits of the integer represent the presence or absence of the keys. For example, if there are two keys 'a' and 'b', and you've collected just 'a', the state might look like 01 (in binary).

As the BFS progresses, we aim to reach a state where state == (1 << k) - 1, which means all k keys have been collected, and the corresponding bits for all keys are set to 1. This check is efficient because (1 << k) - 1 produces a number with the first k bits set to 1.

A key aspect of this solution is the avoidance of duplicate states; we keep a set vis of visited (position, state) pairs to ensure we do not reprocess the same scenarios. Each time a key is picked up, the state changes, and the (position, state) pair is considered unique, allowing further exploration from this new scenario.

The BFS continues until either all keys are collected, or no further movement is possible. The variable ans is used to count the number of moves made, and if the state where all keys have been collected is reached, the corresponding value of ans is returned, indicating the shortest path. If the BFS concludes without collecting all keys, the function returns -1 to indicate that the task is impossible.

Learn more about Breadth-First Search patterns.

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

Which data structure is used in a depth first search?

Solution Approach

The solution to this problem implements a BFS to explore the given grid efficiently. Here is a step-by-step explanation of the approach:

  1. Identify Starting Point and Key Count:

    • Find the cell with the '@' character which is the starting position.
    • Calculate the number of keys k in the grid by counting the lowercase letters.

  2. Initialize BFS Structures:

    • Use a queue q and initialize it with the tuple (si, sj, 0), where si and sj are starting cell coordinates, and 0 represents the initial state with no keys collected.
    • Create a set vis to keep track of the visited cells with particular states to avoid re-processing them. (si, sj, 0) is added to it as an initially visited state.

  3. BFS Algorithm:

    • While the queue is not empty, process each element by popping from the left (dequeue).
    • If the current state reflects all keys have been collected (state == (1 << k) - 1), return the current number of moves ans.
    • Explore all possible movements (up, down, left, right) by adding or subtracting from the current cell coordinates.
    • For each move, check if the potential move is valid (i.e., within bounds, not walking into walls, having the key if it's a lock).
    • When encountering a key, update the state by setting the corresponding bit using a bitwise or operation nxt |= 1 << (ord(c) - ord('a')).
    • After processing all valid movements, increment the ans variable to reflect an increase in the number of moves.

  4. State Management:

    • The state variable is a bitmask representing the keys collected. For example, if there are 6 possible keys, the state could be a number between 0 (no keys) and 63 (all keys, where binary 111111 is 63 in decimal).
    • If a key is found, it modifies the state by setting the corresponding bit to 1.

  5. Avoid Duplicate States:

    • Before enqueueing the new state, check if (x, y, nxt) has not been visited to prevent duplicate processing.
    • If not, add (x, y, nxt) to the vis set and enqueue the new coordinates and state to the queue q.

  6. Check for Solution:

    • The BFS will end in two cases:
      • All keys are collected, and the function returns the minimum number of steps ans.
      • The queue q is empty without all keys collected, indicating there is no solution, and the function returns -1.

The usage of BFS ensures that the shortest path to collect all keys is found because it explores all possible paths simultaneously, branching out in a breadth-first manner. By using a bitmask to represent the collected keys, the solution is both space-efficient and fast, as the check to see if we have all the keys becomes a simple bitwise comparison. The use of a set to track visited states prevents the algorithm from falling into infinite loops or reprocessing unnecessary states, thus ensuring the BFS terminates with the correct answer or -1 if a solution is not possible.

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

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's consider a simple example grid to understand how the solution works:

1# Grid:
2@.a
3.#.
4Ab.

Starting from the @ symbol, the task is to collect the keys represented by lowercase 'a' and 'b', passing through locks 'A' and 'B' if we have the corresponding keys, and determining the minimum number of moves to complete this task.

  1. Identify Starting Point and Key Count:

    • The cell with the '@' character is at coordinates (0, 0).
    • There are two keys 'a' and 'b' in the grid.

  2. Initialize BFS Structures:

    • Initialize the queue q with ((0, 0), 0) indicating that we start at the top-left corner with no keys collected.
    • The set vis starts with ((0, 0), 0) to represent that we've visited the starting position with no keys.

  3. BFS Algorithm:

    • The initial state dequeued from q is ((0, 0), 0). We haven't collected any keys yet (state = 0).
    • From the start, we can go right to the cell (0, 1) with no change in state since it's an empty cell.
    • Next, we can go down to cell (1, 1), but it's a wall, so we ignore this move.

  4. State Management:

    • Move to cell (0, 2), pick up key 'a'. Our state changes to (0, 2), with the state bitmask now being 01.

  5. Avoid Duplicate States:

    • Add this new state to the vis set and push ((0, 2), 01) onto q.

  6. BFS Continues:

    • Continue with BFS, dequeueing ((0, 2), 01) and we see the key 'a' is collected.
    • From this cell, we can move down to (1, 2) next to lock 'A'. Since we have key 'a', we can pass through.
    • From (1, 2), we move left to cell (1, 1) and then down to (2, 1) where key 'b' is located.
    • Now we collect key 'b', and our state bitmask becomes 11.

  7. Check for Solution:

    • The condition (state == (1 << k) - 1) is met since we have two keys and our state bitmask is 11 (in binary), which equals 3 (in decimal) and is equal to (1 << 2) - 1.
    • Calculate the total number of moves: Move right to (0, 1), move right to (0, 2), collect key 'a', move down to (1, 2), move left to (1, 1), move down to (2, 1), and collect key 'b'. This is a total of 6 moves.

The result for this example grid is that the shortest path to acquire all keys is 6 moves. If this process had been continued until the queue was empty without collecting all keys, the result would be -1, indicating that acquiring all keys is not possible.

Solution Implementation

1from collections import deque
2from itertools import pairwise
3
4class Solution:
5    def shortestPathAllKeys(self, grid: List[str]) -> int:
6        m, n = len(grid), len(grid[0])  # Get the dimensions of the grid
7      
8        # Find the starting position
9        start_i, start_j = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')
10      
11        # Count the number of keys in the grid
12        total_keys = sum(cell.islower() for row in grid for cell in row)
13      
14        # Directions for moving up, down, left, and right
15        directions = (-1, 0, 1, 0, -1)
16      
17        # Initialize a queue with the starting position and initial state
18        queue = deque([(start_i, start_j, 0)])
19      
20        # Keep track of visited states: (i, j, state of collected keys)
21        visited = {(start_i, start_j, 0)}
22      
23        # Steps taken so far
24        steps = 0
25      
26        # BFS loop
27        while queue:
28            # Process all positions in the queue at the current step
29            for _ in range(len(queue)):
30                i, j, state = queue.popleft()
31              
32                # If we have collected all keys, return the current number of steps
33                if state == (1 << total_keys) - 1:
34                    return steps
35              
36                # Check all adjacent cells
37                for a, b in pairwise(directions):
38                    x, y = i + a, j + b
39                    next_state = state
40                    # Check if the new position is valid
41                    if 0 <= x < m and 0 <= y < n:
42                        cell = grid[x][y]
43                        # If it's a wall or a locked door without its key, skip
44                        if (
45                            cell == '#' or
46                            cell.isupper() and (state & (1 << (ord(cell) - ord('A'))) == 0)
47                        ):
48                            continue
49                        # If it's a key, add it to the state
50                        if cell.islower():
51                            next_state |= 1 << (ord(cell) - ord('a'))
52                        # If the new position and state haven't been visited, add them to the queue
53                        if (x, y, next_state) not in visited:
54                            visited.add((x, y, next_state))
55                            queue.append((x, y, next_state))
56          
57            # Increment the steps after finishing this level of BFS
58            steps += 1
59      
60        # If we haven't returned by now, there is no possible solution
61        return -1
62
1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    private int[] directions = {-1, 0, 1, 0, -1}; // Used to iterate through neighboring cells
6
7    public int shortestPathAllKeys(String[] grid) {
8        int rows = grid.length; // The number of rows in the grid
9        int cols = grid[0].length(); // The number of columns in the grid
10        int totalKeys = 0; // The total number of keys in the grid
11        int startRow = 0, startCol = 0; // Starting position '@'
12
13        // First, discover the number of keys, and locate the starting position
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                char cell = grid[i].charAt(j);
17                if (Character.isLowerCase(cell)) { // If the cell has a key
18                    ++totalKeys;
19                } else if (cell == '@') { // If the cell is the starting position
20                    startRow = i;
21                    startCol = j;
22                }
23            }
24        }
25
26        // Queue for BFS
27        Deque<int[]> queue = new ArrayDeque<>();
28        // Enqueue starting position with initial state 0 (no keys collected)
29        queue.offer(new int[]{startRow, startCol, 0});
30        // Visit array to avoid revisiting states [row][col][bitmask for keys]
31        boolean[][][] visited = new boolean[rows][cols][1 << totalKeys];
32        visited[startRow][startCol][0] = true;
33
34        int steps = 0; // The number of steps taken to reach the current position
35
36        // BFS loop
37        while (!queue.isEmpty()) {
38            for (int size = queue.size(); size > 0; --size) {
39                int[] currentPosition = queue.poll();
40                int currentRow = currentPosition[0], currentCol = currentPosition[1], keysState = currentPosition[2];
41              
42                // If we've collected all keys, return the number of steps
43                if (keysState == (1 << totalKeys) - 1) {
44                    return steps;
45                }
46
47                // Explore neighbors
48                for (int d = 0; d < 4; ++d) {
49                    int newRow = currentRow + directions[d], newCol = currentCol + directions[d + 1];
50                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
51                        char cell = grid[newRow].charAt(newCol);
52                        // Check if it's a wall or a locked door without the corresponding key
53                        if (cell == '#' || 
54                            (Character.isUpperCase(cell) && ((keysState >> (cell - 'A')) & 1) == 0)) {
55                            continue;
56                        }
57                        int nextKeysState = keysState;
58                        // If it's a key, add it to the states bitmask
59                        if (Character.isLowerCase(cell)) {
60                            nextKeysState |= 1 << (cell - 'a');
61                        }
62                        // If this state hasn't been visited, enqueue it
63                        if (!visited[newRow][newCol][nextKeysState]) {
64                            visited[newRow][newCol][nextKeysState] = true;
65                            queue.offer(new int[]{newRow, newCol, nextKeysState});
66                        }
67                    }
68                }
69            }
70            ++steps; // Increment steps after exploring all positions at the current step level
71        }
72        return -1; // If we're here, there's no path that collects all keys
73    }
74}
75
1class Solution {
2public:
3    // Directions for moving up, right, down, left, up (to cycle through)
4    const static inline vector<int> directions = {-1, 0, 1, 0, -1};
5
6    // Finds the shortest path that collects all keys in a grid
7    int shortestPathAllKeys(vector<string>& grid) {
8        int rows = grid.size(), cols = grid[0].size();
9        int totalKeys = 0; // Track the total number of keys
10        int startRow = 0, startCol = 0; // Starting position
11
12        // Scanning the grid to find the number of keys and starting position
13        for (int i = 0; i < rows; ++i) {
14            for (int j = 0; j < cols; ++j) {
15                char cell = grid[i][j];
16                if (islower(cell)) { // If cell contains a key
17                    ++totalKeys;
18                } else if (cell == '@') { // If cell is the starting point
19                    startRow = i;
20                    startCol = j;
21                }
22            }
23        }
24
25        // Visited state stored as 3D vector with positions and keys state
26        vector<vector<vector<bool>>> visited(rows, vector<vector<bool>>(cols, vector<bool>(1 << totalKeys)));
27        visited[startRow][startCol][0] = true;
28
29        // Queue for BFS: holds state as (row, col, keys bit mask)
30        queue<tuple<int, int, int>> queue;
31        queue.emplace(startRow, startCol, 0);
32
33        int steps = 0; // Number of steps taken
34
35        // Breadth-first search
36        while (!queue.empty()) {
37            for (int size = queue.size(); size > 0; --size) {
38                auto [currentRow, currentCol, keysState] = queue.front();
39                queue.pop();
40
41                // If keysState matches all keys collected, return steps
42                if (keysState == (1 << totalKeys) - 1) return steps;
43
44                // Explore the neighbors in four directions
45                for (int h = 0; h < 4; ++h) {
46                    int newRow = currentRow + directions[h], newCol = currentCol + directions[h + 1];
47
48                    // Check boundaries and obstacles
49                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
50                        char newCell = grid[newRow][newCol];
51
52                        // If it's a wall or a locked door without the key, skip
53                        if (newCell == '#' || (isupper(newCell) && !(keysState >> (newCell - 'A') & 1))) {
54                            continue;
55                        }
56
57                        // Key collection state
58                        int nextKeyState = keysState;
59                        if (islower(newCell)) { // Collect the key
60                            nextKeyState |= 1 << (newCell - 'a');
61                        }
62
63                        // If state is not visited, mark as visited and add to the queue
64                        if (!visited[newRow][newCol][nextKeyState]) {
65                            visited[newRow][newCol][nextKeyState] = true;
66                            queue.emplace(newRow, newCol, nextKeyState);
67                        }
68                    }
69                }
70            }
71            ++steps; // Increment steps after each layer of BFS
72        }
73
74        // If no path found return -1
75        return -1;
76    }
77};
78
1// TypeScript does not have a type equivalent to C++'s std::pair or std::tuple,
2// so we'll create an interface for our queue state elements instead.
3interface QueueState {
4  row: number;
5  col: number;
6  keysState: number;
7}
8
9// Directions array to move up, right, down, left and then up again (to cycle).
10const directions: number[] = [-1, 0, 1, 0, -1];
11
12// Function that finds the shortest path to collect all keys in a grid.
13function shortestPathAllKeys(grid: string[]): number {
14  const rows: number = grid.length;
15  const cols: number = grid[0].length;
16  let totalKeys: number = 0; // Track the total number of keys
17  let startRow: number = 0;
18  let startCol: number = 0; // Starting position
19
20  // Scanning the grid to find the number of keys and starting position
21  for (let i = 0; i < rows; i++) {
22    for (let j = 0; j < cols; j++) {
23      const cell = grid[i][j];
24      if (cell.match(/[a-z]/)) { // If cell contains a lowercase letter, it's a key
25        totalKeys++;
26      } else if (cell === '@') { // If cell contains '@', it's the starting position
27        startRow = i;
28        startCol = j;
29      }
30    }
31  }
32
33  // Visited states stored in a 3D array: positions and key bitmask
34  const visited: boolean[][][] = new Array(rows).fill(0).map(() =>
35    new Array(cols).fill(0).map(() => new Array(1 << totalKeys).fill(false)));
36
37  visited[startRow][startCol][0] = true;
38
39  // Queue for BFS, holding states of type QueueState
40  const queue: QueueState[] = [{ row: startRow, col: startCol, keysState: 0 }];
41
42  let steps: number = 0; // Number of steps taken
43
44  // Breadth-first search
45  while (queue.length > 0) {
46    let size = queue.length;
47    while (size-- > 0) {
48      const { row, col, keysState } = queue.shift()!;
49
50      // If keysState matches all keys collected, return the number of steps
51      if (keysState === (1 << totalKeys) - 1) return steps;
52
53      // Explore the neighbors in four directions
54      for (let h = 0; h < 4; h++) {
55        const newRow: number = row + directions[h];
56        const newCol: number = col + directions[h + 1];
57
58        // Check boundaries and if not a wall or locked door
59        if (newRow >= 0 && newRow < rows &&
60            newCol >= 0 && newCol < cols && 
61            grid[newRow][newCol] !== '#') {
62        
63          const newCell: string = grid[newRow][newCol];
64
65          // Skip locked doors if the key hasn't been collected
66          if (newCell.match(/[A-Z]/) && !(keysState >> (newCell.charCodeAt(0) - 'A'.charCodeAt(0)) & 1)) {
67            continue;
68          }
69
70          // Key collection state update
71          let nextKeysState: number = keysState;
72          if (newCell.match(/[a-z]/)) { // If it is a key, collect it
73            nextKeysState |= 1 << (newCell.charCodeAt(0) - 'a'.charCodeAt(0));
74          }
75
76          // If this state hasn't been visited, mark it as visited and enqueue
77          if (!visited[newRow][newCol][nextKeysState]) {
78            visited[newRow][newCol][nextKeysState] = true;
79            queue.push({ row: newRow, col: newCol, keysState: nextKeysState });
80          }
81        }
82      }
83    }
84    steps++; // Increment steps after each layer of BFS
85  }
86
87  // If no path is found, return -1
88  return -1;
89}
90
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity:

The time complexity of the algorithm is primarily determined by the breadth-first search (BFS) it performs to find the shortest path to collect all keys.

  • The algorithm iterates through each cell in the grid, which gives us an initial O(m*n) complexity.
  • In the worst case, every position on the grid could be visited with every possible key collection state, which is 2^k where k is the number of keys.
  • The for _ in range(len(q)) loop iterates through each element in the queue, which in the worst case can contain all the cells times the number of states, resulting in m*n*2^k.
  • Each cell expands to a maximum of 4 neighboring cells.

Combining these factors, the time complexity is O(m*n*4*2^k) simplified to O(m*n*2^k) as constants are generally omitted in big-O notation.

Space Complexity:

The space complexity involves the space used by the queue and the visited states:

  • The queue could potentially store all cells with each possible key state, which would require O(m*n*2^k) space.
  • The visited set also stores tuples of (row, column, key_state), which will contain at most m*n*2^k entries.

Hence, the space complexity is also O(m*n*2^k).

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

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

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 👨‍🏫