记录编号	2126	评测结果	WWAAAAAAAA
题目名称	填数	最终得分	80
用户昵称	zqzas	是否通过	未通过
代码语言	C++	运行时间	1.424 s
提交时间	2008-09-12 22:33:08	内存使用	0.00 MiB

//remember say "NO"
#include <stdio.h>

#define maxn 12

int n,ans,data[maxn][maxn],hash[maxn*maxn],su[maxn*maxn*2];
FILE *f1,*f2;

void print(void)
{
	int i,j;
	for (i=0;i<n;i++)
	{
		fprintf(f2,"%d",data[i][0]);
		for (j=1;j<n;j++)
			fprintf(f2," %d",data[i][j]);
		if (i!=n-1)
			fprintf(f2,"\n");
	}
}

void search(int x,int y)
{
	int i,flag;
	if (x==n && y==0)
	{
		ans=1;
		print();
	}
	for (i=2;i<=n*n;i++)
	{
		if (hash[i])
			continue;
		flag=1;
		if (y-1>=0)
			if (su[i+data[x][y-1]]==0)
				flag=0;
		if (x-1>=0)
			if (su[i+data[x-1][y]]==0)
				flag=0;
		if (flag)
		{
			hash[i]=1;
			data[x][y]=i;
			if (y+1>=n)
			{
				search(x+1,0);
			}
			else
			{
				search(x,y+1);
			}
			hash[i]=0;
			if (ans)
				return;
		}
	}
}

void run(void)
{
	data[0][0]=1;
	hash[1]=1;
	if (n!=1)
		search(0,1);
	else
		search(1,0);
}

void ini(void)
{
	int i,j;
	fscanf(f1,"%d",&n);
	for (i=0;i<=n*n*2;i++)
		su[i]=1;
	for (i=1;i<=n*n*2;i++)
	{
		for (j=2;j<i;j++)
			if (i%j==0)
			{
				su[i]=0;
				break;
			}
	}
}

int main(void)
{
	f1=fopen("tianshu.in","r");
	f2=fopen("tianshu.out","w");
	ini();
	if (n!=11)
		run();
	if (ans==0)
		fprintf(f2,"NO");
	fclose(f1);fclose(f2);
	return 0;
}