farm irrigation.cpp

农场灌溉问题。用c++实现

#include<iostream.h>
static int key,m,n;
//y数组保存单个模块的信息,如A(1 1 0 0) B(0 1 1 0)-----
//x数组保存输入的单个模块,即如	A B C D----
//parent数组用来检查两个模块是否已经连通,即相当于一个并查集
int match(int i,int j,int k,char x[10][50]);
void findcirle(int m,int n,char x[10][50]);
class unionfindset//并查集类
{
public:
	unionfindset();
	int find(int x);//查找函数
	void uniont(int x,int y);//合并函数
	void chushi();
private:
	int parent[500];
};
unionfindset::unionfindset()
{
//	parent=new int[m*n];
	for(int i=0;i<500;i++)
		parent[i]=-1;
}
void unionfindset::chushi()
{for(int i=0;i<500;i++)	parent[i]=-1;}
int unionfindset::find(int x)
{
	if(parent[x]<0) return x;
	else return find(parent[x]);
}
void unionfindset::uniont(int x,int y)
{parent[y]=x;}
/*void findcirle(int m,int n,char x[10][50])//找圈函数
{ int i,j,z[10][50]={0};
    for(  i=0;i<m;i++)
	{	for(  j=0;j<n-1;j++)
		{
			if(match(i,j,1,x))//当前的i,j变化尤为关键
			{if(i!=m-1){z[i*(n-1)+j][1]=1;if(i!=0){z[(i-1)*(n-1)+j][3]=1;}}
			 else//最下一行的竖列的第0个变成上一行竖列的第三个
                 z[(m-2)*(n-1)+j][3]=1;   
			}
		}
	}
	for( i=0;i<n;i++)
	{	for(  j=0;j<m-1;j++)
		{
		if(match(i,j,2,x))
		{if(i!=n-1){z[j*(n-1)+i][0]=1;if(i!=0){z[j*(n-1)+i-1][2]=1;}}
       	else //最右一行的横列的第0个变成左一列的第三个
		  z[j*(n-1)+n-2][2]=1;
		}
		}
	}
	for(i=0;i<(m-1)*(n-1);i++)
	{
		for(j=0;j<4;j++)
		{cout<<z[i][j]<<"   ";}
		cout<<endl;
	}
}*/
int match(int i,int j,int k,char x[10][50])
{//将y初始化
	int	y[11][4]={1,1,0,0,0,1,1,0,1,0,0,1,
	              0,0,1,1,0,1,0,1,1,0,1,0,
				  1,1,1,0,1,1,0,1,1,0,1,1,
				  0,1,1,1,1,1,1,1};  
	if(k==1)
	{if(y[int(x[i][j]-65)][2]==1&&y[int(x[i][j+1]-65)][0]==1) 
	{return 1;}
	}
	if(k==2)
	{if(y[int(x[j][i]-65)][3]==1&&
	y[int(x[j+1][i]-65)][1]==1) {return 1;}}
	return 0;
}
void main()
{ 
	cout<<"Annotation!!!!:"<<endl;
	cout<<"   The first line contains 2 integer m and n. "<<endl;
	cout<<"   Then m lines follow,every line include n character!!!"<<endl;
	cout<<"   Pleale input munber A---K"<<endl;
	cout<<"   m<0 end your input!!"<<endl;
	cout<<"Now input your informations please!!"<<"  注意行和列 m * n"<<endl;
	int i,j,k,t[10][2];
	char x[10][50],tt[10][500];
	for(k=0;k<10;k++)//初始化t,tt两个数组
	{
		cin>>t[k][0]>>t[k][1];
		if(t[k][0]>=1&&t[k][1]<=50)
		{
		  for(i=0;i<t[k][0];i++)
		  {
			for(j=0;j<t[k][1];j++)
				cin>>tt[k][i*t[k][1]+j];
		  }
		}
		else break;
	}
	k=0;m=t[k][0];n=t[k][1];
	unionfindset T;
	while(t[k][0]>=1&&t[k][1]<=50&&k<10)
	{ 
		for(i=0;i<10;i++)
			for(j=0;j<50;j++) x[i][j]=0;
		key=0;T.chushi();//每一次循环后,都将praent,x,key初始化
		m=t[k][0];n=t[k][1];
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
				x[i][j]=tt[k][i*n+j];
		}
		k++;
		for(i=0;i<m;i++)
		{
			for(j=0;j<n-1;j++)
			{
				if(match(i,j,1,x))
				{T.uniont(i*n+j,i*n+j+1);key++;}
			}
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<m-1;j++)
			{
				if(match(i,j,2,x))
				{
					if(T.find(j*n+i)!=T.find((j+1)*n+i))
					{T.uniont(j*n+i,(j+1)*n+i); key++;}
				}
			}
		}
		cout<<m*n-key<<endl;
	}
    //cout<<int(x[0][0]-65);
    //int	y[11][4]={1,1,0,0,0,1,1,0,1,0,0,1,
	//              0,0,1,1,0,1,0,1,1,0,1,0,
	//			  1,1,1,0,1,1,0,1,1,0,1,1,
	//			  0,1,1,1,1,1,1,1};  
	//cout<<y[int(x[0][0]-65)][2];
	/*for( i=0;i<m;i++)
	{	for( j=0;j<n-1;j++)
		{match(i,j,1,x);}
	}
	for( i=0;i<n;i++)
	{	for( j=0;j<m-1;j++)
		{match(i,j,2,x);}
	}

	cout<<key<<endl;
	findcirle(m,n,x);*/	
}