莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 将二维坐标映射成一维坐标
2. 是否存在环：判断起点和目标点是否在同一个集合
3. 如果在同一个集合就退出循环，否则合并集合

并查集可参考： 合并集合

#include<bits/stdc++.h>

using namespace std;

const int N = 40010;

int n,m;
int p[N];

//把二维坐标映射成一维坐标（1 ～ n * n）
int get(int x,int y)
{
    return (x-1)*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=1;i<=n*n;i++) p[i]=i;

    int res=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        char op;

        cin>>x>>y>>op;

        //获得起点和目标点的一维坐标
        int a=get(x,y);
        int b;
        if(op=='D') b=get(x+1,y); //向下连一条边
        else b=get(x,y+1); //向右连一条边

        //判断是否在同一集合
        if(find(a)==find(b))
        {
            res=i;
            break;
        }

        //合并集合
        p[find(a)]=find(b);
    }

    if(res) cout<<res<<endl;
    else cout<<"draw"<<endl;

    return 0;
}