题目描述 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
4
数据范围及提示 Data Size & Hint
n <= 200
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int map[1001][1001];
5 int now=1;
6 int f[1000001];
7 int find(int x)
8 {
9 if(f[x]!=x)
10 f[x]=find(f[x]);
11 return f[x];
12 }
13 void unionn(int r1,int r2)
14 {
15 f[r2]=r1;
16 }
17 int main()
18 {
19 int ans;
20 int flag=0;
21 int n,m;
22 int x1,y1;
23 int x2,y2;
24 char z;
25 cin>>n>>m;
26 for(int i=1;i<=n;i++)
27 for(int j=1;j<=n;j++)
28 {
29 map[i][j]=now;
30 now++;
31 }
32 for(int i=1;i<=n*n+20;i++)
33 f[i]=i;
34
35 //scanf("%d%d",&n,&m);
36 for(int i=1;i<=m;i++)
37 {
38 cin>>x1>>y1;
39 cin>>z;
40 if(z=='D')
41 {
42 x2=x1+1;
43 y2=y1;
44 }
45 else
46 {
47 x2=x1;
48 y2=y1+1;
49 }
50 int r1=find(map[x1][y1]);
51 int r2=find(map[x2][y2]);
52 if(r1!=r2)
53 unionn(r1,r2);
54 else
55 {
56 flag=1;
57 ans=i;
58 break;
59 }
60
61 }
62 if(flag==1)
63 cout<<ans<<endl;
64 else
65 {
66 cout<<"draw";
67 }
68 return 0;
69 }