# 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â€¦
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.