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

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 ;
}

}

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.