All problems

Shutter Panel Maze

Hard · graph traversal

A warehouse floor is a rectangular grid of cells. Each cell holds one character:

• "." is open floor and "#" is a wall you cannot enter.
• "S" is where you start and "E" is the exit. Each appears exactly once and both count as open floor.
• A lowercase letter "a" to "d" is a floor panel. An uppercase letter "A" to "D" is a shutter. The panel and shutter with the same letter belong together.

Every shutter starts closed, and you cannot walk onto a closed shutter. Each time you step onto a panel cell, all shutters of its letter switch: closed ones open and open ones close. Panels of the same letter all control the same shutters. Stepping off a panel changes nothing, and you can walk onto the same cell as many times as you like (every time you step onto a panel counts). Shutter cells that are open behave like open floor.

Each step moves you one cell up, down, left or right, and never outside the grid. Return the fewest steps needed to get from "S" to "E", or -1 if the exit cannot be reached.

Examples

Example 1

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

Output: 3

Stepping onto the panel opens the shutter "A", so you can walk through it to "E".

Example 2

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

Output: 6

A straight walk crosses both panels, so the shutter opens and then closes again. Instead step onto the first panel, back to the start and onto the first panel again (3 steps), then onto the second (4). The shutter is now open: walk through it (5) to the exit (6).

Example 3

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

Output: 5

Step down onto the panel (2 steps), go back up (3), then through the open shutter (4) to the exit (5).

Constraints

• 1 <= rows, cols <= 25
• Every cell is ".", "#", "S", "E", a panel "a" to "d" or a shutter "A" to "D".
• There is exactly one "S" and one "E". All rows have the same length.