Solution in O(x*y)


#1
#include<bits/stdc++.h>
using namespace std;
float dist(pair<int,int> a,pair<int,int> b){
    float distance=sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
    return distance;
}
class graph{
    map<pair<int,int>,list<pair<int,int>>> l;
public:
    void addedge(pair<int,int> a,pair<int,int> b){
        l[a].push_back(b);
        l[b].push_back(a);
    }
    bool answer(pair<int,int> src,pair<int,int> dest,vector<int> E, vector<int> F,float r,int n,int arr[102][102],int dp[102][102]){
        if(src==dest){
            return true;
        }
        if(dp[src.first][src.second]==1) return true;
        else if(dp[src.first][src.second]==-1) return false;
        bool success=false;
        for(auto i:l[src]){
            if(arr[i.first][i.second]==0){
                 arr[i.first][i.second]=1;
                 if(answer(i,dest,E,F,r,n,arr,dp))
                 success=true;
            }
        }
        if(success) dp[src.first][src.second]=1;
        else dp[src.first][src.second]=-1;
        return success;
    }
};
string Solution::solve(int x, int y, int N, int R, vector<int> &E, vector<int> &F) {
    bool ans;
    graph g;
    float radius=1.0*R;
    int arr[102][102]={0};
    arr[0][0]=1;
    for(int i=0;i<=x;i++){
        for(int j=0;j<=y;j++){
            if(i<x && j<y) g.addedge(make_pair(i,j),make_pair(i+1,j+1));
            if(i<x) g.addedge(make_pair(i,j),make_pair(i+1,j));
            if(j<y) g.addedge(make_pair(i,j),make_pair(i,j+1));
            if(i<x && j>0) g.addedge(make_pair(i,j),make_pair(i+1,j-1));
        }
    }
    for(int m=0;m<=x;m++){
        for(int n=0;n<=y;n++){
            for(int i=0;i<N;i++){
                if(dist(make_pair(m,n),make_pair(E[i],F[i]))<=radius)
                arr[m][n]=2;
            }
        }
    }
    int dp[102][102]={0};
    for(int i=0;i<N;i++)
    if( dist(make_pair(x,y),make_pair(E[i],F[i]))<=radius)
    return "NO";
    ans=g.answer(make_pair(0,0),make_pair(x,y),E,F,radius,N,arr,dp);
    if(ans) return "YES";
    else return "NO";
   
}