题目：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代码