蓝桥集训之格子游戏
#include<iostream>
#include<cstring>
using namespace std;
const int N = 40010; //原本的n 的平方
int p[N];
int n,m;
int getxy(int x,int y)
{
return x*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=0;i<n*n;i++) p[i] = i; //最大n * n
int res=0;
for(int i=1;i<=m;i++)
{
int x,y;
char d;
cin>>x>>y>>d;
x -- , y --; //坐标从0开始才可以转化
int a = getxy(x,y);
int b;
if(d == 'D') b = getxy(x+1,y); //往下走 找下点的坐标
else b = getxy(x,y+1); //找右点的坐标
int pa = find(a) , pb = find(b);
if(pa == pb) //本次成环
{
res = i;
break;
}
else
{
p[pa] = pb;
}
}
if(res == 0) puts("draw");
else cout<<res;
}