HDOJ 1198 Farm Irrigation 题解

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1198 题目大意不再赘述，刚做的时候看了不少网上题解，发现都说的不是很清楚，索性自己写一个。 #include "iostream" #include "cstdio" using namespace std; //结构体，用来表示各种块的连通情况，WASD想必游戏玩家都明白 struct Node { bool w,s,a,d; }node[]= { 1, 0, 1, 0, //A 1, 0, 0, 1, //B 0, 1, 1, 0, //C 0, 1, 0, 1, //D 1, 1, 0, 0, //E 0, 0, 1, 1, //F 1, 0, 1, 1, //G 1, 1, 1, 0, //H 0, 1, 1, 1, //I 1, 1, 0, 1, //J 1, 1, 1, 1//K }; int n,m; char map[51][51]; int pre[2500]; int find(int x) { return pre[x]==x?x:pre[x]=find(pre[x]);//寻找根节点同时路径缩短 } int main() { int i,j,x,y,ans; while(~scanf("%d%d",&n,&m)) { if(n==-1||m==-1)break; ans=n*m; for(i=0;i<n;i++) scanf("%s",map[i]); for(i=0;i<n*m;i++) pre[i]=i; for(i=0;i<n;i++) for(j=0;j<m;j++) { x=find(i*m+j);//节点代号，也就是第一行第一个是0第二个是1，以此类推 if(i-1>=0)//越界判断 { y=find((i-1)*m+j); if(x!=y&&node[map[i][j]-'A'].w&&node[map[i-1][j]-'A'].s)//如果根节点不一样（或是说不在同一个连通块），并且可以想连，则连接，且连通区-1 { ans--; pre[y]=x; } } if(i+1<n) { y=find((i+1)*m+j); if(x!=y&&node[map[i][j]-'A'].s&&node[map[i+1][j]-'A'].w) { ans--; pre[y]=x; } } if(j-1>=0) { y=find(i*m+j-1); if(x!=y&&node[map[i][j]-'A'].a&&node[map[i][j-1]-'A'].d) { ans--; pre[y]=x; } } if(j+1<m) { y=find(i*m+j+1); if(x!=y&&node[map[i][j]-'A'].d&&node[map[i][j+1]-'A'].a) { ans--; pre[y]=x; } } } printf("%d\n",ans); } return 0; }