题目大意

题目大概意思是每次可以从x, y到x+1,y或者x,y+1,如果出现环就输出第几回合出现环的，否则就输出draw。

solution

这道题就是判断出现环的问题，我们假设，当前点是x,y，下一个连接的点,如果两个点的父亲一样，那么就可以确定现在已经出现了环。

并查集写法

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x);
    return p[x];
}

二维数组压缩为一维

由于并查集查找父亲是一个一位坐标，需要把二维数组压缩成为一个维度来表示他的父亲。

当坐标从(0,0)开始的时候，我们可以将d = x * n + y,n就是行数，所以我们就可以这样来表示。

#include <bits/stdc++.h>

using namespace std;
int n, m;
const int N = 4010; /二维压缩过来最多的点的个数
int p[N];
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int get(int x, int y){
    return x * n + y;
}
int main(){
    cin >> n >> m;
    for(int i = 0; i <= n * n; i++) p[i] = i;
    int res = 0;
    for(int i = 1; i <= m; i++){
        int x, y, a, b;
        char op;
        cin >> x >> y >> op;
        x--, y--;
        a = get(x, y);
        if(op == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) p[fb] = fa;
        else{
            res = i;
            break;
        }
    }
    if(!res) puts("draw");
    else cout << res << endl;
    return 0;
}