I was asked this problem in a recent interview and I was not able to come up with the solution so asking for opinions from you all. This is not the exact problem, but the closest possible version of it (nevertheless, it'll help me solve the problem).

Problem statement:

You're given a 2D maze which has some cells blocked denoted by #, empty space denoted by . and exactly 1 exit denoted by E. There will be a rat in a maze which needs to reach the exit cell and it can move up, down, left and right from any cell.

Provide a sequence of moves for the rat so that it can reach the exit cell no matter what starting position of the rat be i.e. the starting point of the rat can be any empty space. While following this sequence, it the rat tries to move to a blocked cell, it will simply ignore that move and take the next move in the sequence. If the rat reaches the exit cell during this sequence of moves, it achieves its goal and will not need to follow the rest of the moves.

Note that all the edges of this maze are blocked, and the input is such that it's always possible to reach the exit cell from every empty space.

Example:

Input:

######
#.#E.#
#....#
######

Answer: Down -> Right -> Right -> Up -> Left

Explanation:

• If the rat starts at position (1, 1), it will go (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (1, 4) -> (1, 3) exit reached.

• If the rat starts at (2, 3), it will go (2, 3) -> (2, 3) down ignored -> (2, 4) -> (2, 4) right ignored -> (1, 4) -> (1, 3) exit reached.

Similarly, we can see that no matter what is the starting position of the rat, it will always reach the exit by following the sequence (and ignoring some moves if it's not possible).

What can be an optimal way to solve this problem? Can this be solved in polynomial time complexity?

TIA