2013
12-04

# Farm Irrigation

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

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.

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.

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

2 2
DK
HF

3 3
FJK
IHE

-1 -1

2
3

//并不需要把四个方向的都判断了
//只要选择其中的两个俄方向就可以
#include<iostream>
#include<cstdio>
#define maxn 51
using namespace std;
//分别表示上下左右四边是否有接口，'0'无，'1'有
char a[11][5]={"1010","1001","0110","0101","1100","0011",
"1011","1110","0111","1101","1111"};
int f[maxn][maxn];
char g[maxn][maxn];
int n,m;
int find(int x)
{
if(f[x/n][x%n]==x)
return x;
return f[x/n][x%n]=find(f[x/n][x%n]);
}
void Union(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
f[y/n][y%n]=x;
}
void judge(int i,int j)//判断g[i][j]和它的左侧上侧是否连通 若连通则合并
{
if(j>0&&a[g[i][j]-'A'][2]=='1'&&a[g[i][j-1]-'A'][3]=='1')
Union(i*n+j,i*n+j-1);
if(i>0&&a[g[i][j]-'A'][0]=='1'&&a[g[i-1][j]-'A'][1]=='1')
Union(i*n+j,i*n+j-n);
}
int main()
{
int i,j,count;
while(scanf("%d%d",&m,&n)!=EOF)
{
if(n==-1&&m==-1)
break;
for(i=0;i<m;i++)
{
scanf("%s",g[i]);
for(j=0;j<n;j++)
f[i][j]=i*n+j;
}
for(i=0;i<m;i++)
for(j=0;j<n;j++)
judge(i,j);
int cnt=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(f[i][j]==i*n+j)
cnt++;
cout<<cnt<<endl;
}
}

1. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。