题目大意
有一个矩阵,两个玩家轮流操作,每次操作是将矩阵中两个相邻的点之间连起来,如果矩阵中出现一个环,游戏结束。输出游戏在第几步结束,若没有结束输出平局。
解题思路
并查集判环问题。什么时候可以断定出现了环?若有一步操作要将$a$与$b$相连,但是$a$与$b$之间已经连通,那么这步操作结束后显然一个环就出现了,游戏结束。此题还涉及了一个很常用的行与列都从$0$开始的二维坐标转一维坐标。
具体代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+10;
int p[N];
int n,m,res;
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int get(int x,int y) //常用的针对行与列下标都从0开始的二维坐标映射一维坐标
{
return x*n+y;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n*n;i++) p[i]=i; //并查集初始化
for(int i=1;i<=m;i++)
{
int x,y;
char d;
cin>>x>>y>>d;
x--,y--; //题干中的矩阵是行与列下标都从1开始,强制改一下
int a=get(x,y);
int b;
if(d=='D') b=get(x+1,y);
else b=get(x,y+1);
//这一步玩家要在a,b间连边
if(find(a)==find(b)) //如果发现a,b已经连通,那么这步结束就有环了,游戏结束
{
res=i;
break;
}
p[find(a)]=find(b); //否则只是单纯连边,玩家继续下一步
}
if(!res) cout<<"draw"<<'\n'; //res没有更新过,说明从始至终都没有出现环
else cout<<res<<'\n';
return 0;
}