大致题意:
见http://www.nocow.cn/index.php/Translate:USACO/castle
大致思路:
苦逼模拟的并查集……usaco里面的还需要输出炸哪一堵墙……崩溃>_<
/*
ID:123ldss2
PROG: castle
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=100005;
int father[nMax],rank[nMax],N,M,num[nMax],sum; //rank近似树的高度。
int find(int x){ // 寻找父节点
if(x!=father[x])
return father[x]=find(father[x]);
return x;
}
void unite(int a,int b){
// cout<<a<<" unio "<<b<<endl;
int x=find(a);
int y=find(b);
if(x==y)
return ;
else{
if(rank[x]>rank[y]){
father[y]=x;
num[x]+=num[y];
}
else if(rank[x]<rank[y]){
father[x]=y;
num[y]+=num[x];
}
else{
father[x]=y;
num[y]+=num[x];
rank[y]++;
}
}
}
void set(){ // 初始化
int i;
for(i=0; i<nMax-1; i++){
father[i]=i;
rank[i]=0;
num[i]=1;
}
//n=0;
}
int map[100][100];
bool vis[nMax];
int main(){
int n,m,i,j,ans1,a,b;
// freopen ( "castle.in", "r", stdin );
// freopen ( "castle.out", "w", stdout );
while(scanf("%d%d",&n,&m)!=EOF){
set();
sum=0;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&map[i][j]);
if((map[i][j]&1)==0){
unite((i-1)*m+j,(i-1)*m+j-1);
}
if((map[i][j]&2)==0){
unite((i-1)*m+j,(i-2)*m+j);
}
if((map[i][j]&4)==0){
unite((i-1)*m+j,(i-1)*m+j+1);
}
if((map[i][j]&8)==0){
unite((i-1)*m+j,(i)*m+j);
}
}
}
ans1=0;
for(i=1;i<=n*m;i++){
j=find(i);
// cout<<"num"<<num[find(i)]<<endl;
ans1=max(ans1,num[find(i)]);
if(vis[j]==0){
vis[j]=1;
sum++;
}
}
cout<<sum<<endl;
cout<<ans1<<endl;
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
poj 1611 The Suspects 代码 并查集的应用
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1754756
NULL 博文链接:https://128kj.iteye.com/blog/1745671
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
这份代码用C++实现了经典算法并查集,来源于poj题目1182
这是西北工业大学的POJ试题的答案,欢迎下载!
poj 2668 Defending Castle.md
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
C + + language learning poj100 question bank and code
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
并查集基础 acm 算法 poj oi 并查集基础.ppt
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138