BFS Solution C++17


#1

const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};
bool vis[1003][1003];
bool valid(int px,int py,int x,int y){
return (px>=0 && py>=0 && px<=x && py<=y && !vis[px][py]);
}
bool dist(int px,int py,int r,vector &e, vector &f,int x,int y){
int sz = e.size();
for(int i=0;i<sz;i++){
int d = (e[i]-px)(e[i]-px) + (f[i]-py)(f[i]-py);
int d2 = (e[i]-x)(e[i]-x) + (f[i]-y)(f[i]-y);
if(r*r>=d)return 0;
}
return 1;
}
bool bfs(int x, int y, int n, int r, vector &e, vector &f){
queue<pair<int,int>> q;
q.push({0,0});
// mp[{0,0}]=1;
while(!q.empty()){
// auto p = q.front();
int px = q.front().first;
int py = q.front().second;
q.pop();
vis[px][py]=1;
// cout<<px<<" “<<py<<”\n";
if(px==x && py==y)return 1;
for(int i=0;i<8;i++){
int x1=px+dx[i];
int y1=py+dy[i];
if(valid(x1,y1,x,y)){
if(dist(x1,y1,r,e,f,px,py)){
q.push({x1,y1});
vis[x1][y1]=1;
if(x1==x && y1==y)return 1;
}
}
}
}
return 0;
}
string Solution::solve(int x, int y, int n, int r, vector &e, vector &f) {
// mp.clear();
memset(vis,0,sizeof(vis));
if(bfs(x,y,n,r,e,f))return “YES”;
return “NO”;
}