A.Artwork Codeforces-Gym102346 2019-10-07 算法竞赛 暂无评论 60 次阅读 题目链接：[https://codeforces.com/gym/102346](https://codeforces.com/gym/102346) ## 题目大意： 一个大小为 m x n 的房间， 有个小偷在（0，0）处，在（m,n）处有一幅画，房间里有 k 个传感器，探测半径为S , 问小偷能否在不被传感器探测到的情况下偷走画，能输出S, 不能输出N. ## 思路 小偷不能到达（m，n） 的情况有4种，就是看所有能相接的圆形成的连通块能否形成下面的形式：  从靠左边（x<=r) 和靠上边 (n-y<=r) 的圆开始dfs , 搜索所有可以连接的圆，若碰到靠右边（m-x<=r) 或靠下（y<=r) 的圆，则小偷无法到达（m,n); 注：被搜过的点不用在搜, 复杂度 O(n)。 ## 代码 ```javascript #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10; int n,m,k; int flag=0; struct node { int x,y,r; }a[N]; bool book[N]; void dfs(int p) { book[p]=1; if(a[p].y<=a[p].r) { flag=1; return ; } if(m-a[p].x<=a[p].r) { flag=1; return ; } for(int i=1;i<=k;i++) { if(!book[i]) { if((ll)(a[p].x-a[i].x)*(a[p].x-a[i].x)+(ll)(a[p].y-a[i].y)*(a[p].y-a[i].y) <=(ll)(a[p].r+a[i].r)*(ll)(a[p].r+a[i].r) ) dfs(i); } } } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>m>>n>>k; for(int i=1;i<=k;i++) { cin>>a[i].x>>a[i].y>>a[i].r; } for(int i=1;i<=k;i++) { if(a[i].x<=a[i].r) { flag=0; dfs(i); if(flag==1) break; } if(n-a[i].y<=a[i].r) { flag=0; dfs(i); if(flag==1) break; } } if(flag==0) cout<<"S"<<endl; else cout<<"N"<<endl; } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭