Help needed in a graph problem

Revision en1, by MasterMind, 2019-09-30 06:54:34

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MasterMind 2019-09-30 06:56:24 4
en1 English MasterMind 2019-09-30 06:54:34 935 Initial revision (published)