题解】"/>
格子游戏【题解】
本文同步发表于:
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;
}
★,°:.☆( ̄▽ ̄)/$:.°★ 。
更多推荐
格子游戏【题解】
发布评论