首页 > 代码库 > hdu 1198 Farm Irrigation

hdu 1198 Farm Irrigation

2024-07-11 05:44:03   228人阅读

Farm Irrigation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5322    Accepted Submission(s): 2290


Problem Description
Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has a different type of pipe. There are 11 types of pipes, which is marked from A to K, as Figure 1 shows.


Figure 1


Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map 

ADC
FJK
IHE

then the water pipes are distributed like 


Figure 2


Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn. 

Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him? 

Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.
 

 

Input
There are several test cases! In each test case, the first line contains 2 integers M and N, then M lines follow. In each of these lines, there are N characters, in the range of ‘A‘ to ‘K‘, denoting the type of water pipe over the corresponding square. A negative M or N denotes the end of input, else you can assume 1 <= M, N <= 50.
 

 

Output
For each test case, output in one line the least number of wellsprings needed.
 

 

Sample Input
2 2DKHF3 3ADCFJKIHE-1 -1
 

      感想：今天的这道花了我一个下午加晚自习吧，本来感觉一个下午就够了，可惜一个坑爹的分号，让我怀疑自己的思路是否正确，然后经过调试，终于发现了那坑爹的分号，改掉它，然后AC，结局还是挺好的。

 

       题意：给你11个小方块，每个小方块上有小水渠，若将一定的方块拼在一起，至少需要多少个水源就可以将所有方块都灌溉到。

 

      解题思路：这道题可以用并查集做，也可以用搜索来做，但我选择了用并查集。若2个方块之间可以连通的话，我们就将其中的一个方块当做儿子加入到另一个方块，并且计数加1。先从上到下从左到右来判断这2个方块是否能连通，若能则将它们合并成一个集合。再者，我们如何知道2个方块是否能够连通，这就的靠我们手动来求解了，先从水平的方向上来看，用一个11*11的矩阵来求解，然后再从竖直方向上来看，同样也是一个11*11的矩阵来求解。还有用来计数的和作为父节点的数组本应该是一个二维数组，但我们可以认为二维数组其实就是一维数组，这样就做完了，剩下的只要认真码代码了。

 

#include <stdio.h>int father[10005], num[10005];int cross[11][11]={{0,0,0,0,0,0,0,0,0,0,0},      //水平方向的方块之间的关系{1,0,1,0,0,1,1,1,1,0,1},{0,0,0,0,0,0,0,0,0,0,0},{1,0,1,0,0,1,1,1,1,0,1},{0,0,0,0,0,0,0,0,0,0,0},{1,0,1,0,0,1,1,1,1,0,1},{1,0,1,0,0,1,1,1,1,0,1},{0,0,0,0,0,0,0,0,0,0,0},{1,0,1,0,0,1,1,1,1,0,1},{1,0,1,0,0,1,1,1,1,0,1},{1,0,1,0,0,1,1,1,1,0,1}};int vertica[11][11]={{0,0,0,0,0,0,0,0,0,0,0},    //竖直方向的方块之间的关系{0,0,0,0,0,0,0,0,0,0,0},{1,1,0,0,1,0,1,1,0,1,1},{1,1,0,0,1,0,1,1,0,1,1},{1,1,0,0,1,0,1,1,0,1,1},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{1,1,0,0,1,0,1,1,0,1,1},{1,1,0,0,1,0,1,1,0,1,1},{1,1,0,0,1,0,1,1,0,1,1},{1,1,0,0,1,0,1,1,0,1,1}};void MakeSet(int n)       //将父节点和计数数组进行初始化{    for(int i = 1; i<=n; i++)    {        father[i] = i;        num[i] = 0;    }}int FindSet(int x)       //查找父节点{    if(x != father[x])    {        father[x] = FindSet(father[x]);    }    return father[x];}void UnionSet(int a, int b)         //将2个集合合并{    int x = FindSet(a);    int y = FindSet(b);    if(x == y)        return ;    if(num[x] >= num[y])    {        father[y] = x;        num[x] += 1;    }    else    {        father[x] = y;        num[y] += 1;    }}int FindC(char a, char b)      //查找水平方向2方块的关系{    return cross[a-65][b-65];}int FindV(char a, char b)      //查找竖直方向2方块的关系{    return vertica[a-65][b-65];}int main(){    int n, m, sum;    char str[55][55];    while(scanf("%d%d", &n, &m)!=EOF && n != -1 && m != -1)    {        for(int i = 1; i<=n; i++)        {            getchar();            for(int j = 1; j<=m; j++)                scanf("%c", &str[i][j]);        }        MakeSet(n*m);        for(int i = 1; i<=n; i++)      //先从左到右将方块合并        {            for(int j = 1; j<m; j++)            {                if(FindC(str[i][j], str[i][j+1]) == 1)     //若存在关系，则合并                {                    UnionSet(i*m+j-m, i*m+j+1-m);                }            }        }        for(int i = 1; i<n; i++)          //从上到下进行方块合并        {            for(int j = 1; j<=m; j++)            {                if(FindV(str[i][j], str[i+1][j]) == 1)      //若存在关系则进行合并                {                    UnionSet(i*m+j-m, i*m+j);                }            }        }        sum = 0;        for(int i = 1; i<=n*m; i++)     //进行累加，求出最小需要的水源个数        {            sum += num[i];        }        printf("%d\n", n*m-sum);    }    return 0;}

 


联系
我们