I had a problem asked to me recently. Given a 2D matrix where '#' represent blocked cell and '.' represent available cells and exit point E. How would you create a set of instructions (Top, Down, Left, Right) that it is always possible to reach exit cell no matter where you start in matrix(it is always possible to reach exit cell from '.')
sorry i cant read my bad
Oh No! I think I was not clear enough but you are already given the maze layout and you should have a common instruction that no matter where you start you always end up in exit cell at the end(or before).
In this maze, ‘E’ isn’t just an exit, it’s the ultimate destination for every dot who’s tired of seeing # all day!
I presume trying to walk in a wall results in no-action (if it results in failure/crash, then it's a very different problem).
I think it's easier to imagine that initially you have a robot placed on each '.' cell, and every time you send an instruction — all robots execute it. Any robot entering E disappears. Then your goal is to move all robots out via E. This is clearly an equivalent problem, you're just simultaneously considering all possibilities.
It is then clear that if two robots occupy the same place at any point, you can thereafter treat them as a single robot (since they will never decouple). So you just need to keep a set of active cells, initially that being all the '.'
Finding any optimal (shortest) sequence of instructions doesn't seem very solvable to me (I could be wrong), but you can probably choose a lot of greedies from here, if the problem is scored partially or is an open-ended interview question. For example, you could repeatedly choose some active cell and move it to E via its shortest path (of course keeping track of all others during this movement and merging them when necessary).
I haven't thought much about efficiency or optimality here, but just giving you an example of a valid generation procedure. If there were any optimality requirements, let us know.
Leetcode biweekly 56 had the same problem. You can check it out If you want a formal editorial.
Sorry but that is an entirely different problem. Please read it carefully.