Shortest Path to Get All Keys

Problem Description

We are given an m x n 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 can move one space at a time in one of the four cardinal directions. You cannot pass through walls and you can only pass through a lock if you have collected its corresponding key. Given that there is exactly one key and one lock for the first k letters, return the fewest number of moves required to collect all the keys. If it is impossible, return -1.

Key Insights

• Use Breadth-First Search (BFS) to explore the grid level by level.
• Represent the collection of keys with a bitmask (since there are at most 6 keys).
• Augment the BFS state with the position (row, col) and the current bitmask of keys collected.
• Use a visited set (or 3D visited structure) to avoid re-exploring the same state.
• Continue exploring until the state where the bitmask equals the target (all keys collected), then return the step count.

Space and Time Complexity

Time Complexity: O(m * n * 2^k) where m and n are the grid dimensions and k is the number of keys. Space Complexity: O(m * n * 2^k) due to maintaining visited states.

Solution

We solve the problem using BFS by treating each grid cell along with the keys collected as a unique state. At each step:

1. If the cell is empty, simply continue.
2. If the cell contains a key, update the key bitmask.
3. If the cell contains a lock, only continue if its corresponding key is already collected.
4. Use a visited set/array to track visited states (row, col, keys). The algorithm terminates when all keys are collected, returning the number of moves. A failure to complete the task returns -1.

Code Solutions