本文主要是介绍HDU 1198——Farm Irrigation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集
先用一个数组a来保存A-K方块上下左右是否有河道。
然后使用并查集，最后判断有多少个不同的集合。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 55
#define M 55
int a[11][4]={ 1,0,0,1, 1,1,0,0,0,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,1 };
char map[N][M];
int father[N*M];
int num[N*M];int GetFather(int x)
{while(father[x]!=-1){x=father[x];}return x;
}void Union(int x,int y)
{int fx=GetFather(x);int fy=GetFather(y);if(fx!=fy)father[fx]=fy;
}int main()
{int n,m;while(~scanf("%d%d",&n,&m)&&n+m>=0){memset(father,-1,sizeof(father));for(int i=0;i<n;i++)cin>>map[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(i>=1&&a[map[i][j]-'A'][0]&&a[map[i-1][j]-'A'][2])//shangUnion(m*i+j,m*(i-1)+j);if(i<n-1&&a[map[i][j]-'A'][2]&&a[map[i+1][j]-'A'][0])//xiaUnion(m*i+j,m*(i+1)+j);if(j>=1&&a[map[i][j]-'A'][3]&&a[map[i][j-1]-'A'][1])//zuoUnion(m*i+j,m*i+j-1);if(j<m-1&&a[map[i][j]-'A'][1]&&a[map[i][j+1]-'A'][3])//youUnion(m*i+j,m*i+j+1); }memset(num,0,sizeof(num));for(int i=0;i<n*m;i++){if(father[i]==-1)num[i]=1;}int ans=0;for(int i=0;i<n*m;i++)if(num[i])ans++;printf("%d\n",ans);}return 0;
}
这篇关于HDU 1198——Farm Irrigation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
