Farm Irrigation
2024-10-18 18:14:54
题目：Farm Irrigation
题目链接：http://210.34.193.66:8080/vj/Problem.jsp?pid=1494
题目思路：并查集
#include<stdio.h>
//并查集重点就是实现：查询某点在哪个集合、将两个集合合并
//查找点的祖先
int a[];
int fun(int x)
{
int p=x;
// 初始化数组 a[i]=i;
// 也就是说当 a[i]==i 时，这是一个祖先，或者他是别人的子树
while(a[p]!=p)
{
p=a[p];
}
// p就是祖先，下面是路径压缩
int q=x;
while(a[q]!=p)
{
x=a[q];
a[q]=p;
q=x;
}
return p;
}
//合并两个集合
void join(int x,int y)
{
int xt=fun(x);
int yt=fun(y);
if(xt!=yt)
{
a[xt]=yt;
}
}
int n,m;
int bian(int i,int j)
{
return i*m+j;
}
int islian_heng(char c1,char c2)
{
if(c1=='B')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else if(c1=='D')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else if(c1=='F')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else if(c1=='G')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else if(c1=='I')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else if(c1=='J')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else if(c1=='K')
{
if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return ;
else return ;
}
else return ;
}
int islian_shu(char c1,char c2)
{
if(c1=='C')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else if(c1=='D')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else if(c1=='E')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else if(c1=='H')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else if(c1=='I')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else if(c1=='J')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else if(c1=='K')
{
if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return ;
else return ;
}
else return ;
}
int main()
{
char s[][];
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==-&&m==-) break;
for(int i=;i<n;i++)
scanf("%s",s[i]);
for(int i=;i<n*m;i++)
a[i]=i;
for(int i=;i<n;i++)
{
for(int j=;j<m-;j++)
{
if(islian_heng(s[i][j],s[i][j+])==)
{
join(bian(i,j),bian(i,j+));
}
}
}
for(int i=;i<m;i++)
for(int j=;j<n-;j++)
if(islian_shu(s[j][i],s[j+][i])==)
{
join(bian(j,i),bian(j+,i));
}
int co=;
for(int i=;i<n*m;i++)
{
if(a[i]==i) co++;
}
printf("%d\n",co);
}
return ;
}
AC代码
最新文章
- Highcharts中国地图热力图
- reborn to freelancer
- 信号量与PV操作
- 01_iOS开发需要准备什么？
- aiku给你们最真心地学习建议--转
- OpenJudge计算概论-求分数序列和
- Ubuntu14.04 Kylin下 GO语言环境搭建
- PHP数组的操作
- VS013的单元测试去哪里了
- 大家帮我测试下,IOCP服务端和客户端交互
- Ubuntu常用软件推荐，图文详细说明及下载
- .net之DateTime
- javascript 面向对象基础 （1）
- svn 批量加入没有加入版本号控制的文件命令
- Django学习手册 - 如何安装django 和 python ？
- day40 mysql数据类型
- 【Tomcat】Tomcat日志切割
- laravel 数据库获取值的常用方法
- java的关键字与保留字
- 在Java API设计中，面向接口编程的思想，以及接口和工厂的关系