C++ O[x * y * N] Neat solution with comments, using BFS, suggestions welcome :)


#1
string Solution::solve(int x, int y, int N, int R, vector<int> &A, vector<int> &B) 
{
    // Declare a 2D character array of size [x + 1][y + 1]
    char rect[x + 1][y + 1];
    bool visited[x + 1][y + 1];
    queue<pair<int, int>> q;
    
    // Fill all area of circle as 'c' to denote circle present
    for(int i = 0; i <= x; i++)
    {
        for(int j = 0; j <= y; j++)
        {
            // Take advantage of this loop to init rect[i][j] as open 'o'
            rect[i][j] = 'o';

            // Take advantage of this loop to init visited of each as false
            visited[i][j] = false;
            
            // Important step
            // Check for each circle if point overlaps
            for(int k = 0; k < N; k++)
            {
                if(sqrt((pow((A[k] - i), 2) + pow((B[k] - j), 2))) <= R)
                {
                    rect[i][j] = 'c';
                }
            }
        }
    }
    
    // Run an iterative BFS from (0,0) using a queue data structure
    q.push(make_pair(0, 0));
    while(!q.empty())
    {
        // Dequeue the front element and check if c or boundary.
        int currx = q.front().first;
        int curry = q.front().second;
        q.pop();
        
        if(currx < 0 or curry < 0 or currx > x or curry > y or 
            visited[currx][curry] or rect[currx][curry] == 'c')
        {
            continue;
        }
        
        // Else, Add it's 8 neighbours to queue
        q.push(make_pair(currx + 1, curry));
        q.push(make_pair(currx - 1, curry));
        q.push(make_pair(currx, curry + 1));
        q.push(make_pair(currx, curry - 1));
        q.push(make_pair(currx + 1, curry + 1));
        q.push(make_pair(currx + 1, curry - 1));
        q.push(make_pair(currx - 1, curry + 1));
        q.push(make_pair(currx - 1, curry - 1));
        
        // Mark current point as visited
        visited[currx][curry] = true;
    }
    
    // Check if destination is visited
    if(visited[x][y])
    {
        return "YES";
    }
    return "NO";
}

Time Complexity: O[x * y * N]
Space Complextiy : O[x * y]