 # A beautiful solution, O(X*Y + N*R) solution

#1

We do not need to block every point inside the circle, we need to only block the perimeter points suitably. Some perimeter may be slightly more than radius from center, for them we will block their neighbours inside the circle. This should not take more than O(perimeter of circle ) points to check which is O®, so this will cost O(N*R) in total.
Then, rest can be done by bfs or dfs, we will check the point is block additionally while seeing path from there,

``````void ch(int &x, int &y, int curr, int x_dir[], int y_dir[]){
x += x_dir[curr];
y += y_dir[curr];
}

bool isInside(int c_x, int c_y, int x, int y, int r){
int dissq = (c_x - x)*(c_x - x) + (c_y - y)*(c_y - y);
return dissq <= r*r;
}

string Solution::solve(int A, int B, int C, int D, vector<int> &E, vector<int> &F) {
queue<pair<int,int> > bfs;
bfs.push(make_pair(0,0));
vector<vector<bool> > visited(A + 1, vector<bool>(B +1, false));
vector<vector<bool> > blocked(A + 1, vector<bool>(B +1, false));
visited = true;
for(int i = 0; i < C; i ++){

int x = E[i], y = F[i] + D;

int x_dir[] = {1, 0, -1, 0};
int y_dir[] = {0, -1, 0, 1};

int curr = 3;

do{
if((abs(x - E[i]) == D) || (abs(y - F[i]) == D))
curr = (curr + 1) % 4;
if((x >= 0) && (x <= A) && (y >= 0) && (y <= B)){
blocked[x][y] = 1;
}
ch(x, y, curr, x_dir, y_dir);
while(!isInside(E[i], F[i], x, y, D)){
for(int x_s = -1; x_s <= 1; x_s ++){
for(int y_s = -1; y_s <= 1; y_s ++){
int xn = x + x_s, yn = y + y_s;
if((xn < 0) || (xn > A) || (yn < 0) || (yn > B))
continue;
blocked[xn][yn] = blocked[xn][yn] | isInside(E[i], F[i], xn, yn, D);
}
}
ch(x, y, (curr + 1) % 4, x_dir, y_dir);
}
}while((D) && ((x != E[i]) || (y != F[i] + D)));

if(isInside(E[i], F[i], 0, 0, D))
return "NO";
}
while(!bfs.empty()){
auto tp = bfs.front();
bfs.pop();
for(int x_s = -1; x_s <= 1; x_s ++){
for(int y_s = -1; y_s <= 1; y_s ++){
if(max(abs(x_s), abs(y_s)) == 0)
continue;
int x = tp.first + x_s, y = tp.second + y_s;
if((x < 0) || (x > A) || (y < 0) || (y > B) || (visited[x][y]) || (blocked[x][y]))
continue;
bfs.push(make_pair(x, y));
visited[x][y] = 1;
}
}
}
string ans_s;
bool ans = visited[A][B];
if(ans)
ans_s = "YES";
else
ans_s = "NO";
return ans_s;
}

``````