We are given a 2D maze that's composed of rooms. We can move from one room to another neighbouring room in all four directions (L,U,R,D). The starting position in the maze is marked using ^ in the maze. Some rooms are blocked which means we cannot navigate to those rooms, these are marked with '#'. There are some rooms which are easy to go, these are marked using an empty space. Some rooms have a door to go inside the room and each of these rooms are marked with a capital alphabet, we can only go through these rooms if we have the corresponding key to this room.Some rooms have keys laying around (for other rooms), which you can collect upon entering that room and use later on to unlock those doors, the room with keys are marked with lower case alphabets. (A room with a door 'A' can be unlocked using key 'a' and so on.)

The question is, return the minimum number of steps taken to collect all keys inside the maze.
(P.S we can re-enter a room as many times, until we have unlocked all the doors or found all the keys).

Eg:
[['^',' ',' ','#'],[' ','#',' ','#'],['b','a',' ','C'],[' ','A','B','c']]

O/P: 10

I used a bfs approach to solve this question but the interviewer was not satisfied and the question itseld had a lot of edge cases which is difficult to figure out in a 35-40 mins interview.

I would like to request anyone who has solved this question before to please share their approach.