#864
Shortest Path to Get All Keys
candidate master · 1310 · lc hard +32 · verified · 54.4% accepted · 2,477 likes · top 47%
Description
You are given an m x n character grid grid containing:
- '.' — an empty cell.
- '#' — a wall.
- '@' — the starting position.
- Lowercase letters — keys.
- Uppercase letters — locks.
Starting at '@', each move walks one step in a cardinal direction. You cannot pass through walls or step outside the grid. Picking up a key allows you to pass through the matching lock.
For some 1 <= k <= 6, the grid contains exactly one key and one lock for each of the first k letters of the alphabet.
Return the minimum number of moves to collect all keys. Return -1 if it is impossible.
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
Code
1
2
3