?? farm irrigation.cpp
字號:
#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);*/
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -