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].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.
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.
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.
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.
| 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. |
Shortest Path to Get All Keys II BFS II Bit Manipulation II BFS Visit More than Once II Leetcode 864 • Aryan Mittal • 7,878 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