MasterMind's blog

Help needed in a graph problem
By MasterMind, history, 5 years ago, In English

we are given a grid of $$$n x m$$$

for example the following grid: You are at position A and you need to move to any of the borders cell. '#' represent a wall while '.' represent an empty spot, 'M' represent a monster. knowing that, each time you take a step, all monsters can take simultaneously a step. The question is there a way to reach one of the borders cell without ever sharing a cell with a monster. You can assume that the monsters already know the path you are taking.

Please read the original statement here

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

Here the answer 

YES
5
RRDDR

I have been thinking about a solution for a while, all my solutions would end up TLE. Any ideas or hint that would help solve this questions?

The link to the problem.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint: You have to check if you can reach any boundary point before any of the monsters. You can use two bfs to calculate this. One with starting node 'A' and the other with multi-source-'M'.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot.. that is all i needed. I did not know about multi source thing, it sounds interesting to me and I will explore it

    → Reply