ZOJ3761（并查集+树的遍历)

Easy billiards

Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge

Edward think a game of billiards is too long and boring. So he invented a new game called Easy billiards.

Easy billiards has N balls on a brimless rectangular table in the beginning, and your goal is try to make the number of balls on the table as least as possible by several hit under the following rules:

1: The direction you hit the balls should parallel to the tables border.

2: If ball A crashed into ball B, ball B will moves in the same direction of ball A before the crashing, and ball A will stop in the place of ball B before the crashing.

3: If ball C is moving and there are no balls in front of ball C, it will runs out of the tables border, that means ball C is out of the table.

4: You can choose arbitrary ball on the table to hit, but on a hit, you can't let the ball you choose to hit runs out of the tables border. In another word, a ball could runs out of the table if and only if it was crashed by another ball in a hitting.

Now, Edward wants to know the least number of balls remained on the table after several hits, and how.

Input

There are multiple test cases. For each test cases, in the first line, there is an integer N, which means the number of the balls on the table. There are following N lines, each line contains two integers Xi and Yi, which means the coordinate of ball I. (0<=N<=2000, 0<=Xi, Yi<=10^8)

Output

For each test cases, you should output the least number of balls on the first line. And you should output several lines to show the order of hits following the first line, each line should contains the coordinate of the ball you choose to hit and the direction you hit. (LEFT,RIGHT,UP,DOWN).

Sample Input

Sample output

1
(2, 2) DOWN
(4, 0) LEFT
(2, 0) LEFT
1
(1, 3) DOWN
(1, 2) DOWN
(2, 3) DOWN
(2, 2) DOWN
(3, 3) DOWN
(3, 2) DOWN
(3, 1) LEFT
(2, 1) LEFT

题意：一块区域内，通过撞球来使区域内球数最少。撞球规则：A球在B球右边而B球右边没球存在，这时，向右撞击A球，A球会撞击B球,A球会停在B球的位置上，B球则被撞出这片区域。
思路：先并查集得到最少撞球数。再DFS遍历树得到撞球方向。
收获：注意标记位置的放法，用链式前向星建无向图。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cstdlib>
  5 using namespace std;
  6 #define maxn 10000
  7 #define maxm 1000000
  8 int n,num;
  9 struct Node
 10 {
 11     int x;
 12     int y;
 13 };
 14 Node node[maxn];
 15 int root[maxn];
 16 void init_root()
 17 {
 18     for(int i=0;i<n;i++)
 19         root[i]=i;
 20 }
 21 int findroot(int x)
 22 {
 23     if(x!=root[x])
 24     {
 25         root[x]=findroot(root[x]);
 26     }
 27     return root[x];
 28 }
 29 void merge_(int a,int b)
 30 {
 31     int x=findroot(a);
 32     int y=findroot(b);
 33     if(x==y)
 34         return;
 35     else
 36         root[y]=x;
 37 }
 38 struct Edge
 39 {
 40     int u,v,next;
 41 };
 42 Edge edge[maxm];
 43 int head[maxm];
 44 int vis[maxm];
 45 void init_edge()
 46 {
 47     num=0;
 48     memset(vis,0,sizeof(vis));
 49     memset(head,-1,sizeof(head));
 50 }
 51 void addedge(int u,int v)
 52 {
 53     edge[num].u=u;
 54     edge[num].v=v;
 55     edge[num].next=head[u];
 56     head[u]=num++;
 57     edge[num].u=v;
 58     edge[num].v=u;
 59     edge[num].next=head[v];
 60     head[v]=num++;
 61 }
 62 void dfs(int pre,int u)
 63 {
 64     //printf("%d%d
",node[u].x,node[u].y);
 65     vis[u]=1;
 66     for(int i=head[u];i!=-1;i=edge[i].next)
 67     {
 68         int v=edge[i].v;
 69         if(!vis[v])
 70         {
 71             dfs(u,v);
 72             //vis[v]=1;
 73         }
 74     }
 75     if(pre!=-1)
 76     {
 77        printf("(%d, %d) ",node[u].x,node[u].y);
 78         if(node[pre].x>node[u].x)
 79             printf("RIGHT
");
 80         if(node[pre].x<node[u].x)
 81             printf("LEFT
");
 82         if(node[pre].x==node[u].x)
 83         {
 84             if(node[pre].y>node[u].y)
 85                 printf("UP
");
 86             else
 87                 printf("DOWN
");
 88         }
 89     }
 90 
 91 }
 92 int main()
 93 {
 94     while(~scanf("%d",&n))
 95     {
 96         for(int i=0;i<n;i++)
 97             scanf("%d%d",&node[i].x,&node[i].y);
 98         init_root();
 99         init_edge();
100         for(int i=0;i<n;i++)
101             for(int j=0;j<i;j++)
102             {
103                 if(node[i].x==node[j].x||node[i].y==node[j].y)
104                     {
105                         merge_(i,j);
106                         addedge(i,j);
107                     }
108             }
109         memset(vis,0,sizeof(vis));
110                 int ans=0;
111         for (int i=0;i<n;i++)
112             if (root[i]==i) ans++;
113             printf("%d
",ans);
114         for(int i=0;i<n;i++)
115             if(root[i]==i)
116             {
117                 dfs(-1,i);
118             }
119     }
120     return 0;
121 }