Maze with Keys and Doors
Hard · Graphs
The maze is an array of equal-length strings. Cells: # wall, . floor, S start, E exit, a–d keys and A–D doors.
You move up, down, left or right, one cell per step. Stepping on a key picks it up (you keep it forever). You can only step on a door if you already hold its lower-case key.
Write shortestPath(grid) that returns the smallest number of steps from S to E, or -1 if the exit cannot be reached.
Hint: breadth-first search where a state is the position PLUS the set of keys held (a bit mask works well).