比赛 20120919dfs 评测结果 AWWTTTTTET
题目名称 虫食算 最终得分 10
用户昵称 Truth.Cirno 运行时间 6.857 s
代码语言 C++ 内存使用 1.94 MiB
提交时间 2012-09-19 20:19:43
显示代码纯文本
#include <cstdio>
using namespace std;

struct rec
{
	int a[30];
	bool f[30];
};

int n,a[30]={0},b[30]={0},c[30]={0},dd;
bool found=false;

rec change(rec r,int pos,int num)
{
	r.a[pos]=num;
	r.f[num]=true;
	return(r);
}

void dfs(rec r,int deep)
{
	int i;
	if (deep==n)
	{
		int temp=0;
		bool able=true;
		for (i=0;i<n;i++)
		{
			dd=r.a[a[4-i]]+r.a[b[4-i]]+temp;
			temp=dd/n;
			dd%=n;
			if (dd!=r.a[c[4-i]])
			{
				able=false;
				break;
			}
		}
		if (able&&!temp)
		{
			found=true;
			for (i=0;i<n-1;i++)
				printf("%d ",r.a[i]);
			printf("%d\n",r.a[n-1]);
		}
		return;
	}
	for (i=0;i<n;i++)
		if (!r.f[i])
		{
			dfs(change(r,deep,i),deep+1);
			if (found)
				return;
		}
}

int main(void)
{
	freopen("alpha.in","r",stdin);
	freopen("alpha.out","w",stdout);
	int i;
	char cha[30]={0},chb[30]={0},chc[30]={0};
	rec r={0};
	scanf("%d\n",&n);
	scanf("%s\n%s\n%s\n",&cha,&chb,&chc);
	for (i=0;i<n;i++)
	{
		a[i]=cha[i]-'A';
		b[i]=chb[i]-'A';
		c[i]=chc[i]-'A';
	}
	dfs(r,0);
	return(0);
}