1022.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
int id[100];int edge[100][100],set[100];
int next[100][8],n,ok;

int find(int d)
{int i;
for(i=0;i<n;i++)
if(id[i]==d)return i;
return -1;
}

int zb[4][2];
/////////////////////////
void search(int i,int axes[4])
{int ax[4],k;
set[i]=1;ok++;

for(k=0;k<4;k++)
{if(axes[k]<zb[k][0])zb[k][0]=axes[k];
 else if(axes[k]>zb[k][1])zb[k][1]=axes[k];
}

int j;
for(j=0;j<n;j++)
if(edge[i][j]!=0&&!set[j])
{for(k=0;k<4;k++)ax[k]=axes[k];

ax[abs(edge[i][j])-1]+=(edge[i][j]>0?1:-1);	
search(j,ax);
}

}
/////////////////
int main()
{int t,i,j,k;int key,ax[4];
cin>>t;
while(t--)
{cin>>n;

for(i=0;i<n;i++)
{cin>>id[i];
for(j=0;j<8;j++)cin>>next[i][j];
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)edge[i][j]=0;
key=1;

for(i=0;i<8&&key;i+=2)
for(j=0;j<n;j++)
{if(next[j][i])
	{k=find(next[j][i]);
	
	if(k<0||id[j]!=next[k][i+1]){key=0;break;}
	else {edge[j][k]=1*(i/2+1);edge[k][j]=-1*(i/2+1);}
	}
}
for(i=0;i<4;i++)zb[i][0]=zb[i][1]=ax[i]=0;

if(key){for(i=0;i<n;i++)set[i]=0;
		ok=0;
		search(0,ax);
		if(ok<n)key=0;
		}
if(key){long v=1;for(i=0;i<4;i++)v*=(zb[i][1]-zb[i][0]+1);
		cout<<v<<endl;}
else cout<<"Inconsistent"<<endl;
}
return 0;
}