Farm Irrigation

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

这题为并查集的联通问题，主要找到能否联通Merge的条件就可以解决

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
int parent[2600];
struct student{int up;int left;int down;int right;
}node[60][60];
int find(int x){if(x != parent[x])parent[x] = find(parent[x]);return parent[x];
}
void Merge(int a,int b){int c = find(a);int d = find(b);if(c != d)parent[d] = c;
}
int main(){int n,m;char ch;while(~scanf("%d %d",&n,&m)){if(n < 0 || m < 0)break;memset(node,0,sizeof(node));for(int i = 1 ; i <= n * m ; i++)parent[i] = i;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= m ; j++){cin>>ch;switch(ch){//结构体联通 case 'A':node[i][j].up = 1;node[i][j].left = 1;break;case 'B':node[i][j].up = 1;node[i][j].right = 1;break;case 'C':node[i][j].left = 1;node[i][j].down = 1;break;case 'D':node[i][j].down = 1;node[i][j].right = 1;break;case 'E':node[i][j].up = 1;node[i][j].down = 1;break;case 'F':node[i][j].left = 1;node[i][j].right = 1;break;case 'G':node[i][j].up = 1;node[i][j].right = 1;node[i][j].left = 1;break;case 'H':node[i][j].up = 1;node[i][j].down = 1;node[i][j].left = 1;break;case 'I':node[i][j].left = 1;node[i][j].right = 1;node[i][j].down = 1;break;case 'J':node[i][j].up = 1;node[i][j].right = 1;node[i][j].down = 1;break;case 'K':node[i][j].down = 1;node[i][j].left = 1;node[i][j].up = 1;node[i][j].right = 1;break;}//联通的条件 if(j >= 2 && node[i][j - 1].right && node[i][j].left)Merge((i - 1) * n + j , (i - 1) * n + j - 1);if(i >= 2 && node[i][j].up && node[i - 1][j].down)Merge((i - 1) * n + j , (i - 2) * n + j);}getchar();}int count = 0;for(int i = 1 ; i <= n * m ; i++){if(find(i) == i)count++;}printf("%d\n",count);}return 0;
}

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

---