A1347 格子游戏 首AC！

特别感谢陈老师和李van宇大蛇给我思路

题意（精简版）

并查集求环（不用管线的颜色，题目没说要弄）

思路

我们小学时学过行程问题，我们一般是靠两者在是否同一点上判断是否相遇

那么是否可以用相同思路求解呢？

在并查集中，相连的两个元素会被并入一个集合。

这也就意味着，在同一集合中的两点之间一定相连

此时，若该两点之间再有一条线段相连，那这就构成了一个封闭图形（线段不与原折线重叠）

举例：

**
**

是一个图 。 设左上角与右下角相连，同时与右上角相连 。

那么，右下角此时与右上角在同一集合。

如果右上角和右下角之间再有一条连线，那么一个封闭图形就构成了。

代码：

#include<bits/stdc++.h>
using namespace std;
int fa[40160];//开一维数组是因为不想改A1346的Get，Merge函数（注意数据范围）
struct node{
	int x;
	int y;
	char dir;//direction（方向）
	int number;
};//多次输入，故用结构体数组存储
node n2[40160];
int Get(int x){
	return x==fa[x]?x:fa[x]=Get(fa[x]); 
}
void Merge(int x,int y){
	fa[Get(x)]=Get(y);
}//并查集基本函数（不懂见A1346）
int main(){
	int n,m;
	scanf("%d%d",&n,&m);//用scanf是因为快，下面的scanf/printf同理
	int m0=m;//这行忘删了，就当是防伪标志
	for(int i=1;i<=n*n;i++){
		fa[i]=i;//一开始，每一个点的父节点都是他自己（我爸竟是我自己😕 ）
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d %c",&n2[i].x,&n2[i].y,&n2[i].dir);//按题目格式输入，这里有点乱
		n2[i].number=(n2[i].x-1)*n+n2[i].y;//二维空间压入一维数组，这里是按从左到右，从上到下的顺序编排的（如果你有别的方式排大可以不抄这里）
	}
	for(int i=1;i<=m;i++){//按步查找
		if(n2[i].dir=='D'){
			if(Get(n2[i].number)==Get(n2[i].number+n)){//判断是否位于同一集合
				printf("%d\n",i);
				return 0;//输入完直接return，免得惹事（反正只有一组数据）
			}
			Merge(n2[i].number+n,n2[i].number);//否则合并
		}
		else if(n2[i].dir=='R'){//与dir=D的情况同理，只是对象要变
			if(Get(n2[i].number)==Get(n2[i].number+1)){
				printf("%d\n",i);
				return 0;
			}
			Merge(n2[i].number+1,n2[i].number);
		}
	}
	printf("draw\n");//因为上面输出完已经return了，所以输不出来的直接输出draw
	return 0;//写完这个直接自信递交！！！（别忘了下面的括号）
}

看在这么辛苦写题解的份上点个赞吧！！！！！！

求你了o(╥﹏╥)o

送一份lzk的风格呆马

#include<iostream>
#include<vector>
#define N 205
using namespace std;
int n,m;
struct edge
{
	int x,y;
	bool operator == (const edge nxt)const
		{return x==nxt.x && y==nxt.y;}
}f[N][N];

edge find(int x,int y)
{
	if(f[x][y]==edge({x,y}))return {x,y};
	return f[x][y]=find(f[x][y].x,f[x][y].y);
}

inline void hb(int x,int y,int a,int b)
{f[find(x,y).x][find(x,y).y]=find(a,b);}

int run()
{
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)f[i][j]={i,j};
	for(int i=1;i<=m;i++)
	{
		int x,y;char f;cin>>x>>y>>f;
		if(f=='D')
			if(find(x,y)==find(x+1,y))return i;
			else hb(x,y,x+1,y);
		else
			if(find(x,y)==find(x,y+1))return i;
			else hb(x,y,x,y+1);
	}
	return -1;
}
int main()
{
	cin>>n>>m;
	int r=run();
	if(r==-1)cout<<"draw";
	else cout<<r;
	return 0;
}

#include <iostream>
using namespace std;
struct node
{ int x,y;}f[301][301],k1,k2;
int i,j,m,n,x,y;
char c;
node root(node k)
{
  if((f[k.x][k.y].x==k.x)&&(f[k.x][k.y].y==k.y))return k;
  f[k.x][k.y]=root(f[k.x][k.y]);
  return f[k.x][k.y];
}
int main()
{
  cin>>n>>m;
  for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
       {f[i][j].x=i;f[i][j].y=j;}
  for(i=1;i<=m;i++)
   {
     cin>>x>>y>>c;
     if(c=='D') {k1=root(f[x][y]);k2=root(f[x+1][y]);}
     if(c=='R') {k1=root(f[x][y]);k2=root(f[x][y+1]);}
     if((k1.x==k2.x)&&(k1.y==k2.y)) {cout<<i<<endl;return 0;}
     else f[k1.x][k1.y]=k2;
    }
  cout<<"draw"<<endl;
  return 0;
}