关键在于如何建图，如何找到相连关系。对每张图片分析就会知道，每块地的水管都是在中间，分为上、下、左、右四个方向可以通水，分两种模式，一种水平相邻，一种竖直相邻，判断他们能不能相通，先预处理得到每两个字符所代表的土地的关系，读入数据后，对应处理，将每块地都编一个标号，就抽象出并查集模型了，最后判断一下有几个点，它的根节点是它自己，就能找到最少需要的水源了。这也是并查集应用之一：判断有几个不相交的集合。
代码 #include#include int up[8], down[8], right[8], left[8];int rank[2504], bin[2504];char map[54][54];char mat1[100][100]; // 上下相连char mat2[100][100]; // 左右相连void prepare(){ int i, j; up[0] = 'A'; up[1] = 'B'; up[2] = 'E'; up[3] = 'G'; up[4] = 'H'; up[5] = 'J'; up[6] = 'K'; down[0] = 'C'; down[1] = 'D'; down[2] = 'E'; down[3] = 'H'; down[4] = 'I'; down[5] = 'J'; down[6] = 'K'; left[0] = 'A'; left[1] = 'C'; left[2] = 'F'; left[3] = 'G'; left[4] = 'H'; left[5] = 'I'; left[6] = 'K'; right[0] = 'B'; right[1] = 'D'; right[2] = 'F'; right[3] = 'G'; right[4] = 'I'; right[5] = 'J'; right[6] = 'K'; memset(mat1, 0, sizeof(mat1)); memset(mat2, 0, sizeof(mat2)); for (i = 0; i <= 6; i++){ for (j = 0; j <= 6; j++){ mat1[down[i]][up[j]] = 1; mat2[right[i]][left[j]] = 1; } }}int find(int x){ if (x != bin[x]){ return bin[x] = find(bin[x]); } return x;}void merge(int x, int y){ int fx, fy; fx = find(x); fy = find(y); if (fx != fy){ if (rank[fx] > rank[fy]){ bin[fy] = fx; }else if (rank[fx] < rank[fy]){ bin[fx] = fy; }else{ bin[fx] = fy; rank[fy]++; } }}int main(){ int M, N, i, j, t1, t2, cnt; prepare(); while (scanf("%d%d", &M, &N) != EOF){ if (M == -1 && N == -1) break; for (i = 0; i < M; i++){ scanf("%s", map[i]); } for (i = 0; i <= M * N; i++){ bin[i] = i; rank[i] = 0; } for (i = 0; i < M; i++){ for (j = 0; j < N; j++){ if (j < N - 1 && mat2[map[i][j]][map[i][j+1]] == 1){ t1 = i * N + j; t2 = i * N + j + 1; merge(t1, t2); } if (i < M - 1 && mat1[map[i][j]][map[i + 1][j]] == 1){ t1 = i * N + j; t2 = (i + 1) * N + j; merge(t1, t2); } } } cnt = 0; for (i = 0; i < M * N; i++){ if (bin[i] == i){ cnt++; } } printf("%d\n", cnt); } return 0;}