Easy Solution using BFS


#1

string Solution::solve(int A, int B, int C, int D, vector &E, vector &F) {
int visited[A+1][B+1];
int x,y;
string yes = “YES”;
string no = “NO”;
for(int i=0;i<=A;i++)
{
for(int j=0;j<=B;j++)
{
visited[i][j] = 0;
}
}

float dist;
for(int i=0;i<=A;i++)
{
    for(int j=0;j<=B;j++)
    {
        for(int k=0;k<C;k++)
        {
            x = E[k];
            y = F[k];
            dist = pow((x-i),2)+pow((y-j),2);
            dist = pow(dist,0.5);
            if(dist <= D) visited[i][j] = 1;
        }
    }
}
queue<pair<int,int>> q;
q.push(pair<int,int>(0,0));
pair<int,int> curr;
while(!q.empty())
{
    curr = q.front();
    q.pop();
    x = curr.first;
    y = curr.second;
    if(visited[x][y]) continue;
    if(x == A && y == B) 
    {
        return yes;
    }
    visited[x][y] = 1;
    if(y+1 <= B)
    {
        if(!visited[x][y+1]) q.push(pair<int,int>(x,y+1));
    }
    if(y-1 >= 0)
    {
        if(!visited[x][y-1]) q.push(pair<int,int>(x,y-1));
    }
    if(x+1 <= A)
    {
        if(!visited[x+1][y]) q.push(pair<int,int>(x+1,y));
        if(y+1 <= B)
        {
            if(!visited[x+1][y+1]) q.push(pair<int,int>(x+1,y+1));
        }
        if(y-1 >= 0)
        {
            if(!visited[x+1][y-1]) q.push(pair<int,int>(x+1,y-1));
        }
    }
    if(x-1 >= 0)
    {
        if(!visited[x-1][y]) q.push(pair<int,int>(x-1,y));
        if(y+1 <= B)
        {
            if(!visited[x-1][y+1]) q.push(pair<int,int>(x-1,y+1));
        }
        if(y-1 >= 0)
        {
            if(!visited[x-1][y-1]) q.push(pair<int,int>(x-1,y-1));
        }
    }
}
return no;

}