直接使用并查集好吧

并查集解决的是连通性（无向图联通分量）和传递性（家谱关系）问题，并且可以动态的维护。抛开格子不看，任意一个图中，增加一条边形成环当且仅当这条边连接的两点已经联通，于是可以将点分为若干个集合，每个集合对应图中的一个连通块。

#include<bits/stdc++.h>
using namespace std;
int n,m,a1,a2,t1,t2,flag;
char t;
int book[205][205];
int zx(int x,int y) {
    if(book[x][y]==x*n+y)
        return book[x][y];
    else
        return book[x][y]=zx(book[x][y]/n,book[x][y]%n);
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            book[i][j]=i*n+j;
    for(int i=1; i<=m; i++) {
        scanf("%d %d %c",&a1,&a2,&t);
        if(flag)
            continue;
        if(t=='D') {
            t1=a1+1;
            t2=a2;
            int c1=zx(a1,a2);
            int c2=zx(t1,t2);
            if(c1==c2)
                flag=i;
            else
                book[c1/n][c1%n]=c2;
        } else {
            t1=a1;
            t2=a2+1;
            int c1=zx(a1,a2);
            int c2=zx(t1,t2);
            if(c1==c2)
                flag=i;
            else
                book[c1/n][c1%n]=c2;
        }
    }
    if(flag)
        cout<<flag<<endl;
    else
        cout<<"draw"<<endl;
    return 0;
}