# Shortest Path to Get All Keys
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-path-to-get-all-keys)
Canonical: https://scaleengineer.com/dsa/problems/shortest-path-to-get-all-keys
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Pinterest](https://scaleengineer.com/companies/pinterest), [Roku](https://scaleengineer.com/companies/roku)
---
## Problem
You are given an `m x n` grid `grid` where:

* `'.'` is an empty cell.
* `'#'` is a wall.
* `'@'` is the starting point.
* Lowercase letters represent keys.
* Uppercase letters represent locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some `1 <= k <= 6`, there is exactly one lowercase and one uppercase letter of the first `k` letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return _the lowest number of moves to acquire all keys_. If it is impossible, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/shortest-path-to-get-all-keys/image0.jpg) 

**Input:** grid = ["@.a..","###.#","b.A.B"]
**Output:** 8
**Explanation:** Note that the goal is to obtain all the keys not to open all the locks.

**Example 2:**

![](https://assets.glich.co/dsa/shortest-path-to-get-all-keys/image1.jpg) 

**Input:** grid = ["@..aA","..B#.","....b"]
**Output:** 6

**Example 3:**

![](https://assets.glich.co/dsa/shortest-path-to-get-all-keys/image2.jpg) 

**Input:** grid = ["@Aa"]
**Output:** -1

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 30`
* `grid[i][j]` is either an English letter, `'.'`, `'#'`, or `'@'`.
* There is exactly one `'@'` in the grid.
* The number of keys in the grid is in the range `[1, 6]`.
* Each key in the grid is **unique**.
* Each key in the grid has a matching lock.

# Approaches
## Brute-Force Depth-First Search
This approach attempts to solve the problem by exploring every possible path from the start point using a Depth-First Search (DFS). It recursively explores adjacent cells, keeping track of the current position, the keys collected (via a bitmask), and the number of steps taken. A global minimum is updated whenever a path that collects all keys is found. However, without memoization (dynamic programming), this method is a brute-force exploration of the state space and is very inefficient.
**Time:** Exponential. The exact complexity is difficult to pin down but is much worse than the optimal solution. It explores a large number of paths in the state graph, many of which are redundant. This will lead to a 'Time Limit Exceeded' verdict. · **Space:** O(m * n * 2^k) in the worst case for the recursion stack depth, where `m` and `n` are grid dimensions and `k` is the number of keys.
**Pros:** Conceptually simple if one is familiar with recursion and backtracking.
**Cons:** Extremely inefficient and will likely time out for most test cases.; It re-explores paths to the same state `(row, col, mask)` multiple times.; The complexity of managing the `visited` state for path-specific tracking can be tricky to implement correctly.
### Explanation
The brute-force DFS algorithm works by trying to find all paths that collect all keys and then picking the shortest one. A recursive function, let's call it `dfs(row, col, mask, steps)`, is the core of this approach.

1.  **State Representation**: The state is defined by `(row, col, mask)`, where `(row, col)` is the current position and `mask` is a bitmask representing the keys collected.
2.  **Recursion**: Starting from the `'@'` position with a mask of `0` and `0` steps, the function explores all four neighbors.
3.  **Path Exploration**: For each valid move (within bounds, not a wall), it checks the cell type:
    *   **Empty ('.') or Start ('@')**: Move to the new cell with the same mask.
    *   **Key ('a'-'f')**: Move to the new cell and update the mask by setting the corresponding bit.
    *   **Lock ('A'-'F')**: Check if the current mask has the required key. If yes, move to the new cell; otherwise, this path is blocked.
4.  **Termination**: When a state is reached where all keys are collected, the current number of steps is compared with a global minimum, and the minimum is updated if the current path is shorter.
5.  **Cycle Prevention**: To avoid getting stuck in loops, a `visited` set must be used. Critically, this set must store the entire state `(row, col, mask)` to distinguish between visiting the same cell with different sets of keys. This `visited` set should track visited states *for the current recursive path only* and backtrack (remove the state) when returning from a recursive call.

This approach is fundamentally flawed for efficiency because it doesn't recognize that the shortest path to a state `(row, col, mask)` is unique. It will repeatedly calculate the path to the same state via different routes, leading to an exponential number of computations.
### Algorithm
*   Define a recursive function, say `dfs(row, col, mask, steps)`.
*   Use a global variable `min_steps` initialized to infinity to store the length of the shortest path found so far.
*   The state of the recursion is defined by the current position `(row, col)` and the bitmask `mask` of collected keys.
*   To avoid infinite loops, use a `visited` set that stores the tuple `(row, col, mask)` for the *current path*. This is crucial; a simple `visited[row][col]` is not enough as a cell might be revisited with a different set of keys.
*   The base case for the recursion is when all keys are collected (i.e., `mask` equals the target mask). At this point, update `min_steps` with the current number of `steps`.
*   Another base case is for pruning: if `steps` already exceeds `min_steps`, terminate that path.
*   In the recursive step, explore all four cardinal directions.
*   For each valid neighbor:
    *   If it's a key, update the mask.
    *   If it's a lock, check if the corresponding key is in the current `mask`.
    *   If the move is permissible, make a recursive call with the updated state and `steps + 1`.
*   This method exhaustively searches all possible paths, which is highly inefficient due to re-computation of paths to the same state.

## Breadth-First Search on State Space
The most efficient way to solve this problem is to view it as a shortest path problem on a state graph. A state is defined not just by the position `(row, col)` but also by the set of keys collected. Since every move has a cost of 1, Breadth-First Search (BFS) is the ideal algorithm. It systematically explores the graph level by level, guaranteeing that the first time we reach a state where all keys are collected, it will be via the shortest possible path.
**Time:** O(m * n * 2^k). Each state `(row, col, mask)` is visited at most once. From each state, we explore 4 neighbors in constant time. · **Space:** O(m * n * 2^k), where `m` and `n` are the grid dimensions and `k` is the number of keys. This space is used for the `visited` array and the queue.
**Pros:** Guaranteed to find the shortest path because BFS explores level by level.; Efficient and optimal for the given problem constraints.; Avoids re-computing paths to the same state `(row, col, mask)` by using a `visited` array.
**Cons:** The space complexity can be high if the grid dimensions or the number of keys were significantly larger.
### Explanation
This approach models the problem as a shortest path search on an unweighted graph where nodes are states. A state is a tuple `(row, col, mask)`.

*   **State Definition**: `(row, col)` represents the current coordinates, and `mask` is an integer bitmask where the i-th bit is 1 if we have the i-th key ('a' + i) and 0 otherwise.
*   **Initialization**: We find the start position `'@'` and count the total number of keys, `k`. The goal is to reach any state with a `mask` of `(1 << k) - 1`.
*   **BFS Setup**: We use a queue to store states to visit and a 3D `visited` array, `visited[row][col][mask]`, to avoid redundant computations and infinite loops. The BFS begins by enqueuing the initial state `(start_row, start_col, 0)`.
*   **Traversal**: The BFS proceeds level by level. In each level, we dequeue all states currently in the queue and generate their successor states. For a state `(r, c, mask)`, we check its four neighbors:
    *   If a neighbor `(nr, nc)` is a wall (`#`), it's ignored.
    *   If it's a lock (`'A'-'F'`), we check if we have the key using the bitmask: `(mask & (1 << (lock - 'A'))) != 0`. If we don't have the key, the move is invalid.
    *   If it's a key (`'a'-'f'`), we calculate a `newMask` by setting the corresponding bit: `newMask = mask | (1 << (key - 'a'))`.
    *   For any valid move that leads to a new state `(nr, nc, newMask)` that has not been visited, we mark it as visited and add it to the queue.
*   **Goal**: The first time we generate a state where the mask equals the target mask, we have found the shortest path. The length of this path is the current level of the BFS. If the queue becomes empty before we find such a state, it means collecting all keys is impossible.

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

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length;
        int n = grid[0].length();
        int startX = -1, startY = -1;
        int keyCount = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    startX = i;
                    startY = j;
                } else if (c >= 'a' && c <= 'f') {
                    keyCount++;
                }
            }
        }

        // State: [row, col, mask]
        Queue<int[]> queue = new LinkedList<>();
        // Visited: visited[row][col][mask]
        boolean[][][] visited = new boolean[m][n][1 << keyCount];

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

        int steps = 0;
        int targetMask = (1 << keyCount) - 1;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        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 mask = current[2];

                if (mask == targetMask) {
                    return steps;
                }

                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];

                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr].charAt(nc) != '#') {
                        char cell = grid[nr].charAt(nc);
                        int newMask = mask;

                        if (cell >= 'a' && cell <= 'f') {
                            // It's a key
                            newMask |= (1 << (cell - 'a'));
                        } else if (cell >= 'A' && cell <= 'F') {
                            // It's a lock
                            if ((mask & (1 << (cell - 'A'))) == 0) {
                                // Don't have the key, cannot pass
                                continue;
                            }
                        }
                        
                        // If this state has not been visited, add to queue
                        if (!visited[nr][nc][newMask]) {
                            visited[nr][nc][newMask] = true;
                            queue.offer(new int[]{nr, nc, newMask});
                        }
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}
```
### Algorithm
*   First, parse the grid to find the starting coordinates `(startX, startY)` and the total number of keys `keyCount`.
*   The state of our search will be `(row, col, mask)`, where `mask` is a bitmask representing the keys collected.
*   Initialize a queue for BFS and add the starting state `(startX, startY, 0)`.
*   Create a 3D boolean array `visited[m][n][1 << keyCount]` to keep track of visited states and prevent cycles. Mark the initial state as visited.
*   The target state is any state where the mask equals `(1 << keyCount) - 1`.
*   Perform a level-order traversal (standard BFS):
    *   Initialize `steps = 0`.
    *   While the queue is not empty, process all nodes at the current level.
    *   For each state `(r, c, mask)` dequeued:
        *   If `mask` is the target mask, we have found the shortest path. Return `steps`.
        *   Explore the four neighbors `(nr, nc)`.
        *   For each valid neighbor (not a wall, within bounds):
            *   Handle the cell type:
                *   **Key**: Calculate `newMask = mask | (1 << (key - 'a'))`.
                *   **Lock**: Check if `mask` has the corresponding key. If not, this move is invalid.
                *   **Empty**: The mask remains unchanged.
            *   If the resulting new state `(nr, nc, newMask)` has not been visited, add it to the queue and mark it as visited.
    *   After processing a full level, increment `steps`.
*   If the queue becomes empty and the target mask was never reached, it's impossible to collect all keys. Return -1.

# Solutions
### Java

```java
class Solution {
private
  int[] dirs = {-1, 0, 1, 0, -1};
public
  int shortestPathAllKeys(String[] grid) {
    int m = grid.length, n = grid[0].length();
    int k = 0;
    int si = 0, sj = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        char c = grid[i].charAt(j);
        if (Character.isLowerCase(c)) {
          ++k;
        } else if (c == '@') {
          si = i;
          sj = j;
        }
      }
    }
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{si, sj, 0});
    boolean[][][] vis = new boolean[m][n][1 << k];
    vis[si][sj][0] = true;
    int ans = 0;
    while (!q.isEmpty()) {
      for (int t = q.size(); t > 0; --t) {
        var p = q.poll();
        int i = p[0], j = p[1], state = p[2];
        if (state == (1 << k) - 1) {
          return ans;
        }
        for (int h = 0; h < 4; ++h) {
          int x = i + dirs[h], y = j + dirs[h + 1];
          if (x >= 0 && x < m && y >= 0 && y < n) {
            char c = grid[x].charAt(y);
            if (c == '#' ||
                (Character.isUpperCase(c) && ((state >> (c - 'A')) & 1) == 0)) {
              continue;
            }
            int nxt = state;
            if (Character.isLowerCase(c)) {
              nxt |= 1 << (c - 'a');
            }
            if (!vis[x][y][nxt]) {
              vis[x][y][nxt] = true;
              q.offer(new int[]{x, y, nxt});
            }
          }
        }
      }
      ++ans;
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const static inline vector<int> dirs = {-1, 0, 1, 0, -1};
  int shortestPathAllKeys(vector<string> &grid) {
    int m = grid.size(), n = grid[0].size();
    int k = 0;
    int si = 0, sj = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        char c = grid[i][j];
        if (islower(c))
          ++k;
        else if (c == '@')
          si = i, sj = j;
      }
    }
    queue<tuple<int, int, int>> q{{{si, sj, 0}}};
    vector<vector<vector<bool>>> vis(
        m, vector<vector<bool>>(n, vector<bool>(1 << k)));
    vis[si][sj][0] = true;
    int ans = 0;
    while (!q.empty()) {
      for (int t = q.size(); t; --t) {
        auto [i, j, state] = q.front();
        q.pop();
        if (state == (1 << k) - 1)
          return ans;
        for (int h = 0; h < 4; ++h) {
          int x = i + dirs[h], y = j + dirs[h + 1];
          if (x >= 0 && x < m && y >= 0 && y < n) {
            char c = grid[x][y];
            if (c == '#' || (isupper(c) && (state >> (c - 'A') & 1) == 0))
              continue;
            int nxt = state;
            if (islower(c))
              nxt |= 1 << (c - 'a');
            if (!vis[x][y][nxt]) {
              vis[x][y][nxt] = true;
              q.push({x, y, nxt});
            }
          }
        }
      }
      ++ans;
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int: m, n = len(grid), len(grid[0]) si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@') k = sum(v . islower() for row in grid for v in row) dirs = (- 1, 0, 1, 0, - 1) q = deque([(si, sj, 0)]) vis = {(si, sj, 0)} ans = 0 while q: for _ in range(len(q)): i, j, state = q . popleft() if state == (1 << k) - 1: return ans for a, b in pairwise(dirs): x, y = i + a, j + b nxt = state if 0 <= x < m and 0 <= y < n: c = grid[x][y] if (c == '#' or c . isupper() and (state & (1 << (ord(c) - ord('A')))) == 0): continue if c . islower(): nxt |= 1 << (ord(c) - ord('a')) if (x, y, nxt) not in vis: vis . add((x, y, nxt)) q . append((x, y, nxt)) ans += 1 return - 1

```