codevs 5972 格子游戏

5972 格子游戏

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

　　Alice和Bob玩了一个古老的游戏：首先画一个n * n的点阵（下图n = 3）　　接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了(n <= 200)，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入描述 Input Description

　　输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行，每行首先有两个数字(x, y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是"D "，则是向下连一条边，如果是"R "就是向右连一条边。输入数据不会有重复的边且保证正确。

输出描述 Output Description

　输出一行：在第几步的时候结束。假如m步之后也没有结束，则输出一行“draw”。

样例输入 Sample Input

3 5

　　1 1 D

　　1 1 R

　　1 2 D

　　2 1 R

　　2 2 D

样例输出 Sample Output

数据范围及提示 Data Size & Hint

见上

这题如果用邻接矩阵做，就必须开的非常大，否则各种RE

 1 #include<cstdio>
 2 #include<iostream>
 3 # define MAXN 10000001
 4 using namespace std;
 5 int father[MAXN];
 6 int m,n;
 7 int find(int x)
 8 {
 9     if(father[x]!=x)
10     {
11         father[x]=find(father[x]);
12         return father[x];
13     }
14     else
15         return x;
16 }
17 void unionn(int i,int j)
18 {
19     father[j]=i;
20 }
21 int main()
22 {
23     ios::sync_with_stdio(false);
24     cin>>n>>m;
25     for(int i=1;i<=n*n;i++)
26         father[i]=i;
27     for(int i=1;i<=m;i++)
28     {
29         int x,y;
30         char c;
31         cin>>x>>y>>c;
32         int r1=(x-1)*n+y;
33         int r2;
34         if(c=='D')
35             r2=r1+n;
36         if(c=='R')
37             r2=r1+1;
38         if(find(r1)==find(r2))
39         {
40             cout<<i;
41             return 0;
42         }
43         else
44             unionn(r1,r2);
45     }
46     cout<<"draw";
47     return 0;
48 }