Lang: C++; Complexity[Time,Space]: [O(A*B*C), O(A*B)]


#1

Idea: Make a matrix of given size. Mark all the matrix cells if they are in the radius of any circle as 0 else -1. Use backtracking to see if (x,y) reachable from (0,0). Cell gets value 1 if (x,y) reachable from that cell.

bool pathExists(vector<vector<int>> &area, int r, int c)
{
    if(r >= area.size() || c >= area[0].size())
        return false;
    else if(r < 0 || c < 0)
        return false;
    
    if(area[r][c] != -1) // processed already
        return area[r][c];
    else
    {
        area[r][c]=0;
        area[r][c] = area[r][c] || pathExists(area,r+1,c-1)	|| pathExists(area,r-1,c-1);
        area[r][c] = area[r][c] || pathExists(area,r+1,c)	|| pathExists(area,r-1,c);
        area[r][c] = area[r][c] || pathExists(area,r+1,c+1)	|| pathExists(area,r-1,c+1);
        area[r][c] = area[r][c] || pathExists(area,r,c+1)	|| pathExists(area,r,c-1);
        return area[r][c];
    }
}
string Solution::solve(int A, int B, int C, int D, vector<int> &E, vector<int> &F) 
{
    if((A < 1 && B < 1) || E.empty() )
        return "YES";
    if(C == (A+1)*(B+1) || D >= A+B+1)
        return "NO";
    
    /* make unprocessed cells = -1 */
    vector<vector<int>> area(A+1, vector<int>(B+1,-1));
    
    /* make cell 0 if in a circle */
    for(int r=0; r<=A; r++)
        for(int c=0; c<=B; c++)
            for(int i=0; i<C; i++)
                if(pow((r-E[i]), 2)+pow((c-F[i]),2)<=pow(D,2))
                    area[r][c] = 0;

    /* If start or end isn't reachable return NO */
    if(area[A][B] * area[0][0] == 0)
        return "NO";

    area[A][B]=1;
    return ((pathExists(area, 0,0)==1)? "YES" : "NO");
}