C++题解——格子游戏

题目链接：一本通 TFLSOJ

思路：使用并查集给点连接，如果在连接过程中遇到已连接的点二次连接，就输出

代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
};
node f[205][205];
int n,m;
node find(node k){
	if(f[k.x][k.y].x==k.x&&f[k.x][k.y].y==k.y)return f[k.x][k.y];
	return f[k.x][k.y]=find(f[k.x][k.y]);
}
void merge(node k1,node k2){
	k1=find(k1);
	k2=find(k2);
	f[k1.x][k1.y]=k2;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j].x=i;
			f[i][j].y=j;
		}
	}
	int x,y;
	char c;
	node k1,k2;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>c;
		if(c=='D'){
			k1=find(f[x][y]);
			k2=find(f[x+1][y]);
		}else{
			k1=find(f[x][y]);
			k2=find(f[x][y+1]);
		}
		if(k1.x==k2.x&&k1.y==k2.y){
			cout<<i;
			return 0;
		}else
			merge(k1,k2);
	}
	cout<<"draw";
	return 0;
}