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.
Auto comment: topic has been updated by MasterMind (previous revision, new revision, compare).
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'.
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