Gym 102346A Artwork dfs

Artwork Gym - 102346A

题意：给n*m的地图，入口是(0,0),出口是(n,m），其中有k个监视器，坐标是(xi,yi)，监视半径是r，问一个人能不能不被监视到，从起点到终点。

如果不能走到终点，无非便是监视范围把路全堵死了，所以开始的想法便是计算几何题，看多个圆能不能把横的和竖的都给覆盖了，但很明显行不通，然后想了想觉得这可以转换成一个图的题。

我们把每个监视器看出点，然后遍历每个监视器跟它相交（相切，包含）的其他点，已经看一下这个圆会涉及到那些边界。然后会把路封死的组合便是，上边界跟左边界，上边界跟下边界，右边界跟下边界，右边界跟左边界。

（也就是上图中五颜六色的线）

所以我们就看每个连通块涉及的边界组合中有没有上述边界。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=1e3+,M=N*N+;

 struct Side{

     int v,ne;

 }S[M<<];

 bool vis[N],book[];

 int n,m,k,sn,head[N],xx[N],yy[N],rr[N];

 void init(){

     sn=;

     for(int i=;i<k;i++){

         head[i]=-;

         vis[i]=false;

     }

 }

 void add(int u,int v){

     S[sn].v=v;

     S[sn].ne=head[u];

     head[u]=sn++;

 }

 int pf(int x){

     return x*x;

 }

 bool judge(int x,int y){

     return pf(xx[x]-xx[y])+pf(yy[x]-yy[y])<=pf(rr[x]+rr[y]);

 }

 void dfs(int u){

     vis[u]=true;

     //0 1 2 3分别代表上 右 下 左 边界

     if(xx[u]-rr[u]<=) book[]=true;

     if(yy[u]+rr[u]>=m) book[]=true;

     if(xx[u]+rr[u]>=n) book[]=true;

     if(yy[u]-rr[u]<=) book[]=true;

     for(int i=head[u],v;~i;i=S[i].ne){

         v=S[i].v;

         if(!vis[v]) dfs(v);

     }

 }

 bool solve(){

     for(int i=;i<k;i++){

         if(vis[i]) continue;

         for(int j=;j<;j++) book[j]=false;

         dfs(i);

         if((book[]||book[])&&(book[]||book[])) return false;

     }

     return true;

 }

 int main(){

     while(~scanf("%d%d%d",&n,&m,&k)){

         init();

         for(int i=;i<k;i++) scanf("%d%d%d",&xx[i],&yy[i],&rr[i]);

         for(int i=;i<k;i++)

             for(int j=i+;j<k;j++) if(judge(i,j)){

                 add(i,j);

                 add(j,i);

             }

         if(solve()) printf("S\n");

         else printf("N\n");

     }

     return ;

 }

小小年纪不学好