ZOJ 3761 Easy billiards 月赛E DFS

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3761

题目大意：给定n个位置的小球，小球的运动方向只能是水平或者竖直的。按一定方向推动某球，当行径上有其他球时，停留在被撞球的位置，被撞的球沿原小球运动方向运动，当行径路径上没有其他球时，该小球被剔除。问：只能通过小球的相撞来剔除小球，最少能留下几个小球。

解题思路：首先，可以用并查集找出互相连通的小球集合个数。因为每一次推动的结果可以看成是被推动的小球被剔除了，其他位置上的小球不动，所以可以从每个集合中任选一个小球作DFS。选择推动小球的方向即为该球指向其父亲节点的方向。

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int set[];

 int e,first[],next[],v[];

 bool vis[];

 struct node

 {

     int x,y,l,id;

 }p[],q[];

 bool cmp1(node a,node b)

 {

     if(a.x==b.x)

         return a.y<b.y;

     return a.x<b.x;

 }

 bool cmp2(node a,node b)

 {

     if(a.y==b.y)

         return a.x<b.x;

     return a.y<b.y;

 }

 void link(int a,int b)

 {

     v[e]=b;

     next[e]=first[a];

     first[a]=e++;

 }

 int find(int x)

 {

     if(set[x]==x)

         return x;

     else return set[x]=find(set[x]);

 }

 void UN(int a,int b)

 {

     int aa,bb;

     aa=find(a);

     bb=find(b);

     if(aa==bb)

         return;

     else

         set[aa]=set[bb];

 }

 void solve(int now)

 {

     int k;

     for(int i=first[now];i!=-;i=next[i])

     {

         k=v[i];

         if(!vis[k])

         {

             vis[k]=true;

             if(q[now].x==q[k].x)

             {

                 if(q[now].y>q[k].y)//up

                     q[k].l=;

                 else

                     q[k].l=;//down

             }

             else

             {

                 if(q[now].x>q[k].x)//right

                     q[k].l=;

                 else

                     q[k].l=;//left;

             }

             solve(k);

         }

     }

     if(q[now].l==)

         printf("(%d, %d) LEFT\n",q[now].x,q[now].y);

     else if(q[now].l==)

         printf("(%d, %d) RIGHT\n",q[now].x,q[now].y);

     else if(q[now].l==)

         printf("(%d, %d) UP\n",q[now].x,q[now].y);

     else if(q[now].l==)

         printf("(%d, %d) DOWN\n",q[now].x,q[now].y);

      return;

 }

 int main()

 {

     int n,j,i,lef[],ans;

     while(~scanf("%d",&n))

     {

         memset(first,-,sizeof(first));

         memset(vis,false,sizeof(vis));

         e=;ans=;

         for(i=;i<n;i++)

         {

             p[i].id=i;

             scanf("%d%d",&p[i].x,&p[i].y);

             q[i].x=p[i].x;q[i].y=p[i].y;

             q[i].l=-;

         }

         for(i=;i<n;i++)

             set[i]=i;

         sort(p,p+n,cmp1);//按x从小到大排序

         for(i=;i<n;i++)

         {

             if(p[i].x==p[i-].x)

             {

                 link(p[i].id,p[i-].id);

                 link(p[i-].id,p[i].id);

                 UN(p[i].id,p[i-].id);

             }

         }

         sort(p,p+n,cmp2);

         for(i=;i<n;i++)

         {

             if(p[i].y==p[i-].y)

             {

                 link(p[i].id,p[i-].id);

                 link(p[i-].id,p[i].id);

                 UN(p[i].id,p[i-].id);

             }

         }

         for(i=;i<n;i++)

         {

             if(set[i]==i)

                 lef[ans++]=i;

         }

         cout<<ans<<endl;

         for(i=;i<ans;i++)

         {

             vis[lef[i]]=true;

             solve(lef[i]);

         }

         // cout<<e<<endl;

     }

     return ;

 }

巴特西

ZOJ 3761 Easy billiards 月赛E DFS

最新文章

热门文章