I was asked this question in an interview and I couldn't solve it.
I would be really grateful if you could help me solve it.
The problem is as follows:-
You are given a rectangular region whose left and bottom-most co-ordinate is (0,0) and right-most and top-most co-ordinate is (x,y).
There are n circles with given center co-ordinates that exist inside the region all having the same radius 'r'.
You are currently standing at (0,0) and want to reach (x,y) without touching any circle.
You have to tell if it is possible or not.
He told me that you can move between 2 points freely and it is not necessary to move along the x or y-axis.
The solution I thought of involved taking a matrix of x*y dimension and for each circle, mark the points which lie inside it or touch it.
After that apply BFS starting from (0,0) to check if we can reach (x,y).
He told me BFS will be wrong which I couldn't figure out why.
I had assumed that circles are having integer radius and have integer co-ordinates.
He also asked me to solve the question without these assumptions.
I couldn't. When asked, he told me it's a standard problem and I should be able to find it on google.
I couldn't, again. Please help!
I think 2 circles can only block the path if the distance between their centers is less than 2r. So it should be enough to build "islands" of overlapping circles and check if any island blocks the path from 0 to (x,y), i.e. if any circles in it intersect rectangle borders in such a way that a straight line between those intersection points would block the path.