{{{ #!cplusplus //hdu 1198 并查集 //2009年5月20日16:50:13 //题目大意:一块地需要浇水,而每块的都又16种不同的土地浇灌系统中的多块组成 // 求不同种组合的浇灌系统组成的地需要多少个浇水机才能浇灌完成 //解题思路:我使用的是并查集的方法,首先用一个一维数组begning[]来存储输入进来的farm样式 // 再用farm[i][4]来表示这块地左上右下的联通情况,根据这和思想来判断这两块地是否连通 // 最后用并查集思想来判断整块地被分成了几块! //自己出现的问题:我刚开始把begning和map的数组开得太小了 //by zjd #include #include using namespace std; int farm[11][4]= {//左中右下 {1,1,0,0}, {0,1,1,0}, {1,0,0,1}, {0,0,1,1}, {0,1,0,1}, {1,0,1,0}, {1,1,1,0}, {1,1,0,1}, {1,0,1,1}, {0,1,1,1}, {1,1,1,1} }; int map[5000]; int m,n; char c; int begning[5000]; void Merge(int x,int y){ int xx=x; int yy=y; while(map[xx]!=-1){ xx=map[xx]; } while(map[yy]!=-1){ yy=map[yy]; } int t; int i=x; while(map[i]!=-1){ t=map[i]; map[i]=xx; i=t; } int j=y; while(map[j]!=-1){ t=map[j]; map[j]=yy; j=t; } if(yy!=xx){ map[yy]=xx; } } int main(){ int i,j; while(scanf("%d%d",&m,&n)!=EOF&&(m!=-1&&n!=-1)){ getchar(); memset(map,-1,sizeof(map)); for(i=0;i