算法：一维数组并查集。

核心算法：先明确在并查集中，每个集合都有一个头，初始化时，集合的头就是他自己。

int a[50000];//只要大于200*200即可。
1（初始化）
    int d,b,n,m,i;//d,b为进行D操作时的行列坐标,n为矩阵大小，m为操作次数
    char c;
    for( i=1;i<=n*n;i++)//为n*n列的每一个结点赋值，初值等于它的下标，也就是每个结点的头就是他自己。
    a[i]=i;

2（找头结点的函数）
int find(int x){
   if(a[x]!=x)a[x]=find(a[x]) ;//如果a[x]不等于x,也就是a[x]的头不是他自己，递归查找他的头，并缩短路径，用a[x]的头给a[x]赋值。
   return a[x];//返回a[x]//返回的是a[x]的头。
}

3.在进行D,R操作前，先判断是否还差一步就可以结束游戏，如果进行相应的D,R操作后，游戏结束，输出循环次数i。
    for( i=1;i<=m;i++){
        int x1;//x1储存当前操作在矩阵中的下标。
        cin>>d>>b>>c;
        x1=(d-1)*n+b;//x1+n表示下一列，x1+1表示下一个坐标。
        if(find(x1)==find(x1+n)&&c=='D'){//判断在经行D操作前x1和即将要操作的x1+n这个集合的头是否是同一个头，如果是则输出当前循环次数i，结束游戏。
            cout<<i<<endl;
            return 0;
        }
        else if(find(x1)==find(x1+1)&&c=='R'){//同理
            cout<<i<<endl;
            return 0;
        }
        if(c=='D'){//进行相应的D,R操作。
        a[find(x1)]=find(x1+n);//将x1的头和x1+n的头连接起来成为一个集合，因为是要给下标为x1的头的集合赋值，所以是a[find(x1],不能是find(x1)=find(x1+n)。
        }
        else
        a[find(x1)]=find(x1+1);//同理
        }

时间复杂度

缩短路径后近似于o（1）。

参考文献

bilibili UP主：哩风

C++ 代码

#include<iostream>
using namespace std;
int a[50000];
int find(int x){
   if(a[x]!=x)a[x]=find(a[x]) ;
   return a[x];
}
int main(){
    int d,b,n,m,i;
    char c;
    cin>>n>>m;
    for( i=1;i<=n*n;i++)
    a[i]=i;
   for( i=1;i<=m;i++){
        int x1,x2;
        cin>>d>>b>>c;
        x1=(d-1)*n+b;
        if(find(x1)==find(x1+n)&&c=='D'){
            cout<<i<<endl;
            return 0;
        }
        else if(find(x1)==find(x1+1)&&c=='R'){
            cout<<i<<endl;
            return 0;
        }
        if(c=='D'){
        a[find(x1)]=find(x1+n);
        }
        else
        a[find(x1)]=find(x1+1);
    }cout<<"draw";

}