You are given an m x n grid grid where:
'.' is an empty cell.'#' is a wall.'@' is the starting point.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:
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:
Input: grid = ["@..aA","..B#.","....b"] Output: 6
Example 3:
Input: grid = ["@Aa"] Output: -1
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 30grid[i][j] is either an English letter, '.', '#', or '@'. '@' in the grid.[1, 6].Problem Overview: You are given a grid representing a maze with walls, keys, and locks. Starting from @, move in four directions and collect all keys while only passing through locks if you already hold the matching key. The goal is to return the minimum number of steps required to collect every key.
Approach 1: Breadth-First Search (BFS) with State Tracking (O(m*n*2^k) time, O(m*n*2^k) space)
This problem is fundamentally a shortest path search on a grid, which makes Breadth-First Search the natural starting point. The tricky part is that the player's state depends not only on the current cell but also on which keys have been collected. Encode the keys using a bitmask (for example, bit i represents key 'a'+i). Each BFS state becomes (row, col, keyMask). When you move onto a key cell, update the mask using bit manipulation. A visited set must track all three components to avoid revisiting the same location with the same key set. The search stops once the mask equals the target mask containing all keys.
Approach 2: A* Search Algorithm (O(m*n*2^k) worst case, typically faster in practice; O(m*n*2^k) space)
A* search improves exploration efficiency by prioritizing promising states. Instead of a plain queue, use a priority queue ordered by f(n) = g(n) + h(n), where g(n) is the distance traveled and h(n) estimates the remaining distance to collect keys. A simple heuristic is the Manhattan distance to the nearest remaining key in the matrix. The state representation remains (row, col, keyMask). The heuristic guides the search toward key locations earlier, reducing unnecessary exploration compared with standard BFS on larger grids.
Approach 3: Bidirectional Search (BFS) (O(m*n*2^k) time, O(m*n*2^k) space)
Bidirectional BFS attempts to reduce search depth by exploring from both ends simultaneously. One frontier expands from the starting position while another represents states where all keys are collected. Each state still tracks (row, col, keyMask). When the frontiers intersect, the shortest path is found. The complexity remains similar to standard BFS, but in practice it can shrink the search space when the grid is large and the number of keys is small.
Recommended for interviews: BFS with state tracking is the expected solution. It clearly models the grid traversal and key collection constraints using a bitmask state. Showing a brute-force mindset first (treating each key combination as a state) demonstrates understanding, but implementing the optimized BFS with (row, col, mask) proves you can translate that idea into an efficient algorithm.
This approach uses a Breadth-First Search (BFS) to explore the grid. The idea is to treat the grid like a graph, where each cell is a node, and transitions between them are edges. Since we can pick up keys and unlock doors, each state is defined by the current position in the grid and the set of keys we have collected so far. The BFS will explore all possible moves, and we store the visited states to prevent redundant processing. The search continues until all keys are collected or all possible states are exhausted.
The Python solution implements a BFS to explore the grid. It uses a queue to store current states, defined by position and keys collected. The solution initializes by finding the starting position and counting all keys needed. The BFS loop processes each state, trying all possible moves, and keeps track of visited states to prevent cycles. When all keys are collected, the function returns the steps taken; if exploration is exhausted and not all keys are collected, it returns -1.
Python
Time Complexity: O(m * n * 2^k), where m and n are the dimensions of the grid and k is the number of keys.
Space Complexity: O(m * n * 2^k), due to the visited states tracking.
This approach uses the A* search algorithm, which is similar to BFS but uses a heuristic to prioritize nodes that appear most promising. The heuristic can be the number of keys left to collect or the Manhattan distance to nearest unexplored keys. Like BFS, we define states by position and keys collected, and employ a priority queue to explore states in an order influenced by the heuristic. This modification aims to reduce the time spent searching unproductive paths.
The Python solution applies the A* search technique. We use a priority queue to handle states, including heuristic-driven priority. States are evaluated based on current path cost and estimated remaining cost, guided by the heuristic that counts keys not collected yet. The solution efficiently navigates the grid, updating keys collected and prioritizing paths that bring us closer to the final state. If paths are exhausted without collecting all keys, the solution returns -1.
Python
Time Complexity: O(m * n * 2^k), where m and n are the grid dimensions and k is the number of keys. The heuristic aids in reducing the actual search space.
Space Complexity: O(m * n * 2^k), since states are tracked in the priority queue.
This approach attempts to optimize the BFS by implementing a bidirectional search. Starting a BFS from both the starting point and from the theoretical point where all keys are collected, the search works concurrently from both ends hoping to meet sooner, theoretically reducing the effective search space.
This C++ solution follows a similar path to the BFS approach but refines it with bidirectional BFS. Starting the BFS from the initial grid position and theoretically completing goal states, it uses a queue to manage and traverse levels. Each possible path through grid updating states based on reachable keys. Like the unidirectional BFS but optimized from exploring both ends.
C++
Time Complexity: The expected complexity can still be O(m * n * 2^k) but theoretically with bidirectional capabilities lowering the average active search space time.
Space Complexity: Also O(m * n * 2^k) due to potential full state coverage retaining visited states for bidirectional expansion points.
According to the problem description, we need to start from the initial position, move in four directions (up, down, left, right), collect all keys, and finally return the minimum number of moves required to collect all keys. If it is not possible to collect all keys, return -1.
First, we traverse the 2D grid to find the starting position (si, sj) and count the number of keys k.
Then, we can use Breadth-First Search (BFS) to solve this problem. Since the number of keys ranges from 1 to 6, we can use a binary number to represent the state of the keys, where the i-th bit being 1 indicates that the i-th key has been collected, and 0 indicates that the i-th key has not been collected.
For example, in the following case, there are 4 bits set to 1, indicating that keys 'b', 'c', 'd', 'f' have been collected.
1 0 1 1 1 0
^ ^ ^ ^
f d c b
We define a queue q to store the current position and the state of the collected keys, i.e., (i, j, state), where (i, j) represents the current position, and state represents the state of the collected keys. The i-th bit of state being 1 indicates that the i-th key has been collected; otherwise, it indicates that the i-th key has not been collected.
Additionally, we define a hash table or array vis to record whether the current position and the state of the collected keys have been visited. If visited, there is no need to visit again. vis[i][j][state] indicates whether the position (i, j) and the state of the collected keys state have been visited.
We start from the initial position (si, sj), add it to the queue q, and set vis[si][sj][0] to true, indicating that the initial position and the state of the collected keys 0 have been visited.
During the BFS process, we take out a position (i, j, state) from the front of the queue and check whether the current position is the endpoint, i.e., whether the current position has collected all keys, which means the number of 1s in the binary representation of state is k. If so, we return the current number of steps as the answer.
Otherwise, we move from the current position in four directions (up, down, left, right). If we can move to the next position (x, y), we add (x, y, nxt) to the queue q, where nxt represents the state of the keys at the next position.
Here, (x, y) must first be within the grid range, i.e., 0 leq x < m and 0 leq y < n. Secondly, if the position (x, y) is a wall, i.e., grid[x][y] == '#', or the position (x, y) is a lock but we do not have the corresponding key, i.e., grid[x][y] >= 'A' && grid[x][y] <= 'F' && (state >> (grid[x][y] - 'A') & 1) == 0), then we cannot move to the position (x, y). Otherwise, we can move to the position </code>(x, y).
If the search ends and we have not collected all keys, return -1.
The time complexity is O(m times n times 2^k), and the space complexity is O(m times n times 2^k). Here, m and n are the number of rows and columns of the grid, respectively, and k is the number of keys.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) with State Tracking | Time Complexity: O(m * n * 2^k), where m and n are the dimensions of the grid and k is the number of keys. |
| A* Search Algorithm | Time Complexity: O(m * n * 2^k), where m and n are the grid dimensions and k is the number of keys. The heuristic aids in reducing the actual search space. |
| Bidirectional Search (BFS) | Time Complexity: The expected complexity can still be O(m * n * 2^k) but theoretically with bidirectional capabilities lowering the average active search space time. |
| State Compression + BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with State Tracking (Bitmask) | O(m*n*2^k) | O(m*n*2^k) | General solution for grid shortest path with collectibles and locks |
| A* Search Algorithm | O(m*n*2^k) worst case | O(m*n*2^k) | Large grids where heuristic guidance can reduce exploration |
| Bidirectional BFS | O(m*n*2^k) | O(m*n*2^k) | When search depth is large and meeting in the middle reduces traversal |
Shortest Path to Get All Keys II BFS II Bit Manipulation II BFS Visit More than Once II Leetcode 864 • Aryan Mittal • 8,819 views views
Watch 9 more video solutions →Practice Shortest Path to Get All Keys with our built-in code editor and test cases.
Practice on FleetCode