AcWing 1250. 格子游戏
原题链接
简单
作者:
京扈
,
2023-03-23 19:51:23
,
所有人可见
,
阅读 134
#include <bits/stdc++.h>
using namespace std;
const int N=40010;
int n,m;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void merge(int x,int y)
{
p[find(x)]=find(y);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n*n;i++)
p[i]=i;
char c;
int a,b;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
int x=(a-1)*n+b;
int y;
if(c=='D') y=a*n+b;
else y=(a-1)*n+b+1;
if(find(x)==find(y))
{
cout<<i<<endl;
return 0;
}
merge(x,y);
}
cout<<"draw"<<endl;
return 0;
}