题解】"/>

格子游戏【题解】

本文同步发表于：
CSDN
AcWing
luogu

【一本通 并查集】格子游戏

原题链接：Accoders2014，一本通1347，acwing1252

原题

【输入样例】

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

【输出样例】

4

算法

并查集

题意

先判断两点是否在一个并查集中，如是，即已创建出一个圈，如否，把连成线的两点坐标放入并查集，继续下一步操作。

解法

简单并查集，就是需要把xy坐标转换成一个数字，也就是 x ∗ n + y x*n+y x∗n+y的映射，另外每次输入的xy坐标需要减去一。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[1010];
int toint(int x,int y){//把坐标映射为一个数字return x*n+y;
}
int find(int x){//并查集模板if(a[x]==x) return x;return a[x]=find(a[x]);
} 
int main(){int x,y;char c;cin>>n>>m;for(int i=1;i<=n*n;i++) a[i]=i;for(int i=1;i<=m;i++){cin>>x>>y>>c;x--,y--;if(c=='D'){int fa=find(toint(x,y)),fb=find(toint(x+1,y));if(fa!=fb) a[fa]=fb;else{cout<<i;return 0;}}else{int fa=find(toint(x,y)),fb=find(toint(x,y+1));if(fa!=fb) a[fa]=fb;else{cout<<i;return 0;}			}}cout<<"draw";return 0;
}

★,°:.☆(￣▽￣)/$:.°★ 。