本文共 1865 字，大约阅读时间需要 6 分钟。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn = 51;int root[maxn * maxn];int m, n, sum;int type[11][4] = {
  {
  1, 0, 1, 0}, {
  1, 0, 0, 1}, {
  0, 1, 1, 0}, {
  0, 1, 0, 1}, {
  1, 1, 0, 0}, {
  0, 0, 1, 1}, {
  1, 0, 1, 1}, {
  1, 1, 1, 0}, {
  0, 1, 1, 1}, {
  1, 1, 0, 1}, {
  1, 1, 1, 1}};       //11种连通方式（每种方式四个接口）char graph[maxn][maxn];int Find(int x) //查找根节点 并 压缩路径{    return root[x] == x ? x : root[x] = Find(root[x]);}int Merge(int x, int y)     //连接{    x = Find(x);    y = Find(y);    if(x == y)        return 0;    else    {        root[x] = y;        return 1;    }}int main(){    while(~scanf("%d %d", & m, & n) && m >= 0 && n >= 0)    {        sum = n * m;            //假设所有块都不相通 则最多需要sum泉眼        for(int i = 0; i < sum; i ++)            root[i] = i;        //初始根数组        for(int i = 0; i < m; i ++)            scanf("%s", graph[i]);        for(int i = 0; i < m; i ++)        {            for(int j = 0; j < n; j ++)            {                if(i > 0 && type[graph[i][j] - 'A'][0] && type[graph[i - 1][j] - 'A'][1])   //判断 这一块 与 上面那一块 是否可以连通（这块可以通上 上块可以通下）                    sum -= Merge(i * n + j, (i - 1) * n + j);   //若是可以连接 则可以少一个泉眼                if(j > 0 && type[graph[i][j] - 'A'][2] && type[graph[i][j - 1] - 'A'][3])   //判断 这一块 与 左边那一块 是否可以连通（这块可以通左 左块可以通右）                    sum -= Merge(i * n + j, i * n + j - 1);     //若是可以连接 则可以少一个泉眼            }        }        printf("%d\n", sum);    }    return 0;}
      
     
    
   

题意：

给你一块地，这块地被分割成许多小正方形，每个正方形中都安装了水管，不同的正方形中可能安装的水管不同，一共有11种水管，分别用字母A~K表示，某些正方形地块的中心有水源，问你至少需要多少个水管，以保证整个正方形农田都能被灌溉。

题解：

（摘自 RainCry）这道题的整个思路都是按着这篇博客写的，我觉得这是很好的一种方法， 简单明了， 之前写的都比较复杂冗长。

转载地址：http://actpi.baihongyu.com/