Find if a path exists in a grid covered with circles of same radius

Question

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!

Answer 1

The interviewer is wrong on the part that BFS cannot be used. Whenever you step into a cell, check that if the cell is within a circle or not, by checking the cell's distance from every other circle centers available to you, if it is within dist<=R then that cell can't be reached from the present particular cell. I solved the similar question present in interviewbit - https://www.interviewbit.com/problems/valid-path/ The code is simple -

   public class Solution {
private class Pair
{
    int x ; int y ;
}
ArrayList<Integer> xindex ; ArrayList<Integer> yindex ; int R ;int len ;
public String solve(int x, int y, int n, int r, ArrayList<Integer> xi, ArrayList<Integer> yi) {
    int dp[][] = new int[x+1][y+1] ;
    len = xi.size() ;
    for(int i=0;i<=x;i++)
    {
        for(int j=0;j<=y;j++)
        dp[i][j] = -1 ;
    }

    xindex = xi ; yindex = yi ;
    dp[0][0] = 1 ; R = r*r ;
    LinkedList<Pair> q = new LinkedList<Pair>() ;
    Pair obj = new Pair() ;
    obj.x = 0 ; obj.y = 0 ;
    q.add(obj) ;
    int arr1[] = {1,1,1,0,-1,-1,-1,0} ;
    int arr2[] = {-1,0,1,1,1,0,-1,-1} ;

    while(q.size()!=0)
    {
        Pair temp = q.poll() ;
        int x1 = temp.x ;
        int x2 = temp.y ;

        for(int i=0;i<8;i++)
        {
            int t1 = x1+arr1[i] ; int t2 = x2+arr2[i] ;

            if((t1>=0)&&(t1<=x)&&(t2>=0)&&(t2<=y))
            {
                if(dp[t1][t2]==-1)
                {
                    boolean res = isValidIndex(t1,t2) ;
                    if(res==false)
                    dp[t1][t2] = 2 ;
                    else
                    {
                        dp[t1][t2] = 1 ;
                        Pair t = new Pair() ;
                        t.x = t1 ; 
                        t.y = t2 ;
                        q.add(t) ;
                    }
                }
            }
        }

        if(dp[x][y]!=-1)
        break ;
    }

    if(dp[x][y]==1)
    return "YES" ;

    return "NO" ;

}

public boolean isValidIndex(int x,int y)
{
    for(int i=0;i<len;i++)
    {
        int x1 = xindex.get(i) ; int x2 = yindex.get(i) ;
        if((x==x1)&&(y==x2))
        return false ;

        int n = (x1-x)*(x1-x) + (x2-y)*(x2-y) ;

        if(n<=R)
        return false ;
    }
    return true ;
}

}

Answer 2

If two circles are touching, draw a line segment between their centers. If a circle touches an edge of the rectangle, joint its center to its projection on the closest side. Then discard the circles. This doesn't modify the connexity of the obstacles and you have turned the problem to the more famliar one of a planar straight line subdivision.

An approach could be by decomposing the domain in slabs, i.e. drawing horizontal lines through every center to partition the plane in trapezoids. Then by a seed filling approach, one can determine the starting slab and extend accessibility to the slabs that have a common horizontal side with it, until either a closed region is filled or the exit slab is reached.

Below, an intermediate step of seed filling from the top-left slab.

If the circle centers are on a regular grid, standard seed filling can do.

Answer 3

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.