PACMAN help

can anyone help how to deal with magical points in this problem?
i know that it can be solved using simple dfs and diameter concept without magical points.

1 Like

Can u share the approach how to solve without magical points, I don’t know how to solve…
Please share any similar question.
Thanks

take any random point a and search for the maximum manhattan distance point from that point (say b) … and again search maximum distance point from b (say c) … now lets say distance between b and c is x … our answer will be ceil(x/2);
it takes linear time O(N).
Try this one - https://www.codechef.com/PLIN2020/problems/SPCWAR

1 Like

but in this question there is no point in 2-d.Do you know nay question where 20d point is given and then we find a integer point…
thanks

idea is same…take maximum distance between any two nodes in graph in all connected components separately…it will be distance between two end points of diameter in each connected component…and take maximum among all connected components

I dont remember any 2d point question

Thanks for replying and sharing question.