<–先点赞

题目描述

传送门

C++ 代码

#include<bits/stdc++.h>
using namespace std;

//并查集
const int N=40010;
int n,m;
int p[N];
int get(int x,int y){//二维转一维
    return x*n+y;
}
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n*n;i++){//点阵大小是n*n
        p[i]=i;//父节点都是本身
    }
    int res=0;
    for(int i=1;i<=m;i++){
        int x,y;
        char d;
        cin>>x>>y>>d;
        x--,y--;//下标从零开始
        int a=get(x,y);//转一维
        int b;
        if(d=='D'){
            b=get(x+1,y);//向下
        }
        else{
            b=get(x,y+1);//向右
        }
        int pa=find(a),pb=find(b);
        if(pa==pb){//如果成环
            res=i;
            break;
        }
        p[pa]=pb;//连接
    }
    if(res==0){//没有成环
        cout<<"draw";
    }
    else{
        cout<<res;
    }
    return 0;
}