思路:
每次连线时,合并一次集合即可
每次连线,会有一个 from 和 to, 判断这两个点是否在一个连通块内即可
如果pa == pb ,代表在一个连通块,那么成环,游戏结束
这里 设 行坐标为 x, 列坐标为 y
x >= 1, y >= 1, x <= n, y <= n.
则 (x,y) 的编号 为 (x-1)*n + y
那么 3x3 的编号 为
1,2,3
4,5,6
7,8,9
注意 x要 -1
如果 是 x*n + y 可能会出问题
4,5,6
7,8,9
10,11,12
代码如下:
#include<iostream>
#include<unordered_map>
using namespace std;
using PII = pair<int,int>;
const int MAXN = 5e4+10;
int fa[MAXN];
unordered_map<char,PII> dirs = {
{'D',{1,0}},
{'R',{0,1}}
};
int n,m;
void init(){
for(int i = 1;i <= n * n;i++){
fa[i] = i;
}
}
int find(int x){
if(fa[x] == x){
return x;
}
return fa[x] = find(fa[x]);
}
int main(){
cin >> n >> m;
init();
int i = 1;
for(;i <= m;i++){
int a,b;
char d;
cin >> a >> b >> d;
int x = (a - 1) * n + b;
int na = a + dirs[d].first;
int nb = b + dirs[d].second;
int y = (na - 1) * n + nb;
int px = find(x);
int py = find(y);
if(px == py){
break;
}else{
fa[px] = py;
}
}
if(i <= m){
cout << i << endl;
}else{
cout << "draw" << endl;
}
return 0;
}