All problems

Keys and Doors

Hard · graph traversal

You are given a maze as a rectangular grid of characters:

• "." is an open floor cell and "#" is a wall you cannot enter.
• "S" is where you start and "E" is the exit. Both appear exactly once and both count as floor.
• A lowercase letter "a" to "d" is a key. Walking onto its cell picks it up. You keep every key you pick up for the rest of the walk, and a key can open any number of doors.
• An uppercase letter "A" to "D" is a door. You can walk onto a door cell only if you already hold the key with the same letter (door "B" needs key "b"). A door never changes the cells around it.

Each step moves you one cell up, down, left or right, and never outside the grid. You may walk over the same cell as many times as you like. A key letter appears at most once, a door letter may appear several times, and a maze may contain doors without a matching key or keys without a matching door.

Return the fewest steps needed to get from "S" to "E". If the exit cannot be reached, return -1.

Examples

Example 1

Input: grid = [["S", ".", ".", "#"], ["#", "#", ".", "#"], ["E", "A", "a", "."]]

Output: 6

The only way to the exit is through door "A". Walk right, then down onto the key "a" (4 steps), then left through the door to "E" (2 more steps).

Example 2

Input: grid = [["S", "#", "E"], ["b", "A", "."]]

Output: -1

The only route goes through door "A", and the key "b" does not open it. There is no key "a" in the maze.

Example 3

Input: grid = [["S", ".", ".", "A", "E"], ["#", "#", "a", "#", "#"]]

Output: 6

Step down onto the key "a" and back up (2 extra steps), then walk through the door. The cell above the key is visited twice.

Constraints

• 1 <= rows, cols <= 25
• Every cell is ".", "#", "S", "E", a key "a" to "d" or a door "A" to "D".
• There is exactly one "S" and one "E". Each key letter appears at most once.
• All rows have the same length.