Help needed in a graph problem
Difference between en1 and en2, changed 4 character(s)
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](https://cses.fi/problemset/task/119
24)↵

~~~~~↵
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](https://cses.fi/problemset/task/119
24) 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)