Блог пользователя DarkSilver

Navigate maze from any available cell to exit[HELP]
Автор DarkSilver, история, 3 месяца назад, По-английски

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 '.')

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 месяца назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

sorry i cant read my bad

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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).

    → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In this maze, ‘E’ isn’t just an exit, it’s the ultimate destination for every dot who’s tired of seeing # all day!

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

write a bfs function that finds the shortest path to E then record each visited node in that path, from there somehow write a set of instructions?

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

(this is my idea but I'm not sure of it) If walking into the wall is illegal, then most of the time it's impossible, but if it leads to nothing happening (I'll assume you don't need the optimal solution), you need to use the walls to your advantage to get everything to the same spot, and after reaching any common spot, it's obvious you can move to E from there. Now to check how to do that, you might want to check if there's a "common direction" (the available cells look like a line of any thickness) so you can move everything in 1 direction and be sure no illegal moves happen, another way you might do it is imagine it like a game of 4096 kind of like what Enchom described (not sure of anything though)

→ Ответить