Shortest Path to Get All Keys
Hard · Queue & Deque · about 35 minutes
Asked at Google, Amazon, Uber, Airbnb, Booking.com, Expedia Group.
In a grid, '@' is the start, '.' empty, '#' a wall, lowercase letters are keys and uppercase letters are the matching locks (there are k ≤ 6 keys, the first k letters). You can walk through a lock only with its key. Return the fewest moves to collect all keys, or -1.