解题思路
并查集
当最后一步连线的两个端点都在同一个并查集中时,则形成了一个环
小技巧
我们的棋盘是二维的,而我们的并查集需要处理 一维的数据,因此要进行一个映射
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=210;
int n,m;
int f[N][N];
int cnt;
int p[N*N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++,cnt++)
{
f[i][j]=cnt;
p[cnt]=cnt;
}
for(int i=1;i<=m;i++)
{
int x,y;
char op[3];
cin>>x>>y>>op;
if(*op=='R')
{
int a=find(f[x][y]),b=find(f[x][y+1]);
if(a!=b)
{
p[a]=b;
continue;
}
else
{
cout<<i<<endl;
return 0;
}
}
else
{
int a=find(f[x+1][y]),b=find(f[x][y]);
if(a!=b)
{
p[a]=b;
continue;
}
else
{
cout<<i<<endl;
return 0;
}
}
}
puts("draw");
return 0;
}