hdu 1198 Farm Irrigation(并查集)

本文主要是介绍hdu 1198 Farm Irrigation(并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

        链接：点击打开链接

题意：

思路：

代码：

#include<iostream>
#include<cstdio>
using namespace std;char a[11][5]={"1010","1001","0110","0101","1100","0011","1011","1110","0111","1101","1111"};
int father[51][51];
char map[51][51];
int n,m;int findset(int x)
{int fx = x/n;int fy = x%n;if(father[fx][fy]!=x)father[fx][fy]=findset(father[fx][fy]);return father[fx][fy];
}
void mergeset(int x,int y)
{x=findset(x);y=findset(y);if(x!=y)father[y/n][y%n]=x;
}
void judge(int i,int j)
{if(j>0 && a[map[i][j]-'A'][2]=='1' && a[map[i][j-1]-'A'][3]=='1')mergeset(i*n+j,i*n+j-1);if(i>0 && a[map[i][j]-'A'][0]=='1' && a[map[i-1][j]-'A'][1]=='1')mergeset(i*n+j,(i-1)*n+j);
}int main()
{//freopen("input.txt","r",stdin);int i,j,cnt;while(scanf("%d%d",&m,&n) != EOF && (n!=-1||m!=-1)){cnt = 0;for(i=0; i<m; i++){scanf("%s",map[i]);for(j=0; j<n; j++)father[i][j]=i*n+j;}for(i=0; i<m; i++)for(j=0; j<n; j++)judge(i,j);for(i=0; i<m; i++)for(j=0; j<n; j++)if(father[i][j]==i*n+j)cnt++;printf("%d\n",cnt);}return 0;
}

大牛博客： 点击打开链接

-----------------------------------------------------------------------------------------------

我想了一个下午还是没思路，tm是dfs还是并查集啊，搞不出来。。。。。

------------------------------------------------------------------------------------------------

战斗，永不停歇~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

这篇关于hdu 1198 Farm Irrigation(并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---