C++ dynamic programming solution


#1

Time Complexity: O(XYN)

string Solution::solve(int x, int y, int C, int r, vector<int> &E, vector<int> &F) {
    int i, j, k, n=E.size();
    vector<pair<int, int>> aux(n, {0,0});
    vector<vector<bool>> dp(y+1, vector<bool>(x+1));
    vector<pair<int, int>> moves={{0,1},{0,-1},{-1,0},{1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
    for(i=0; i<n; i++)
        aux[i]={E[i], F[i]};
    dp[0][0]=1;
    for(i=0; i<n; i++){
        int x1=aux[i].first, y1=aux[i].second;
        if(x1*x1+y1*y1<=r*r){
            dp[0][0]=0; 
            break;
        }
    }
    for(i=0; i<=y; i++){
        for(j=0; j<=x; j++){
            if(dp[i][j]){
                for(auto m:moves){
                    int a=i+m.first;
                    int b=j+m.second;
                    bool flag=true;
                    if(a>=0 && a<=y && b>=0 && b<=x){
                        for(auto elt:aux){
                            int x1=elt.first, y1=elt.second;
                            if((x1-b)*(x1-b)+(y1-a)*(y1-a)<=r*r){
                                flag=false;
                                break;
                            }
                        }
                        dp[a][b]=flag;
                    } 
                }
            }
        }
    }
    return dp[y][x] ? "YES" : "NO";
}