题目描述

Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？
输入格式
输入数据第一行为两个整数 n 和 m。n表示点阵的大小，m 表示一共画了 m 条线。

以后 m 行，每行首先有两个数字 (x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 D，则是向下连一条边，如果是 R 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式
输出一行：在第几步的时候结束。

假如 m 步之后也没有结束，则输出一行“draw”。

数据范围

1≤n≤200，
1≤m≤24000

输入样例：

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

输出样例：

4

直接使用并查集，将点的坐标映射为1个数，然后将画一笔看成起点和终点连通，最后查看什么时候形成了连通块即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
map<pair<int,int>,int> M;
const int MAXN = 24100;
int F[MAXN];
int getF(int x){
    return F[x] == x ? x : F[x] = getF(F[x]);
}
int _union(int x,int y){
    x = getF(x);
    y = getF(y);
    if(x != y) F[x] = y;
}
bool issame(int x, int y){
    return getF(x) == getF(y);
}
int n,m,t;
int main(){
    for(int i = 0; i < MAXN; i++) F[i] = i;
    char s[4];
    cin >> n >> m;
    int ans = -1;
    for(int i = 0; i < m; i++){
        int x,y,x1,y1;
        cin >> x >> y >> s;
        if(s[0] == 'D'){
            x1 = x+1;
            y1 = y;
        }else{
            x1 = x;
            y1 = y+1;
        }
        if(!M.count({x,y}))M[{x,y}] = t++;
        if(!M.count({x1,y1})) M[{x1,y1}] = t++;
        if(issame(M[{x,y}],M[{x1,y1}])){
            if(ans == -1) ans = i+1;
        }
        _union(M[{x,y}],M[{x1,y1}]);
    }
    if(ans == -1){
        printf("draw\n");
    }else{
        printf("%d\n",ans);
    }
    return 0;
}