iprakhar22's blog

How to solve this constructive maze problem
By iprakhar22, history, 3 months ago, In English

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

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by iprakhar22 (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Do you need to minimize the length of the sequence? It is not clear from the post. If not, the following algorithm will work in polynomial time.

$$$V = $$$ set of all empty cells. $$$S = $$$ empty string.

While $$$V$$$ is not empty:

  1. Pop $$$v \leftarrow V$$$.
  2. Execute $$$S$$$ starting from $$$v$$$. Let the end vertex be $$$v'$$$.
  3. Find a path from $$$v'$$$ to the exit. Call this path $$$T$$$.
  4. Append $$$T$$$ to $$$S$$$.

Clearly the correctness holds, and the running time is polynomial.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    No, you need not minimize the output sequence length. You just need to construct any one possible sequence as per the problem requirements.

    Your solution definitely works, and this is what I was looking for. Thank you. It took me some time to see the correctness in your approach, but it's definitely a very easy approach to this problem.

    → Reply