alpha.cpp

虫食算程序

#include<stdio.h>

int n;
char *a,*b,*c;
bool* flag_num;
bool* flag_char;
int *num;


bool Scan(int index,int addin){
	bool flag_c=false;
	int i;	
	
	if(index<0){
		for(i=0;i<n;i++)
			printf("%2d ",num[i]);
		printf("\n");	
		return true;
	}

	if(!flag_char[a[index]]){
		for(i=0;i<n;i++){
			if(!flag_num[i])
				continue;
			flag_char[a[index]]=true;
			num[a[index]]=i;
			flag_num[i]=false;
			if(Scan(index,addin))
				return true;
			flag_num[i]=true;
			flag_char[a[index]]=false;
		}
	}

	if(!flag_char[b[index]]){
		for(i=0;i<n;i++){
			if(!flag_num[i])
				continue;
			flag_char[b[index]]=true;
			num[b[index]]=i;
			flag_num[i]=false;
			if(Scan(index,addin))
				return true;
			flag_num[i]=true;
			flag_char[b[index]]=false;
		}
	}

	if(!flag_char[c[index]]){
		i=(num[a[index]]+num[b[index]])%n;
		i=(i+addin)%n;
		if(flag_num[i]){
			flag_char[c[index]]=true;
			num[c[index]]=i;
			flag_num[i]=false;
			flag_c=true;
		}
	}
	for(i=0;i<index;i++){
		if((flag_char[a[i]])&&(flag_char[b[i]])&&(flag_char[c[i]])){
			int tempa,tempb,tempc;
			tempa=num[a[i]];
			tempb=num[b[i]];
			tempc=num[c[i]];
			if( ((tempa+tempb)%n!=tempc)&&((tempa+tempb+1)%n!=tempc)){
				if(flag_c){
					flag_num[num[c[index]]]=true;
					flag_char[c[index]]=false;
				}
				return false;
			}
		}
	}
	if((flag_char[a[index]])&&(flag_char[b[index]])&&(flag_char[c[index]])){
		int tempa,tempb,tempc;
		tempa=num[a[index]];
		tempb=num[b[index]];
		tempc=num[c[index]];
		if( ((tempa+tempb+addin)%n==tempc)){
			if(Scan(index-1,(tempa+tempb+addin)/n))
				return true;
		}
	}

	if(flag_c){
		flag_num[num[c[index]]]=true;
		flag_char[c[index]]=false;
	}
	return false;
}

int main()
{
	int i;
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);

	num=new int[n];
	a=new char[n];
	b=new char[n];
	c=new char[n];
	flag_num=new bool[n];
	flag_char=new bool[n];

	scanf("%s",a);
	scanf("%s",b);
	scanf("%s",c);

	for(i=0;i<n;i++){
		a[i]-='A';
		b[i]-='A';
		c[i]-='A';
		flag_num[i]=true;
		flag_char[i]=false;
		num[i]=-1;
	}
	Scan(n-1,0);
	return 0;
}