求助P1549
  • 板块灌水区
  • 楼主星空舞涵
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/8/27 10:13
  • 上次更新2023/11/6 19:12:47
查看原帖
求助P1549
243750
星空舞涵楼主2020/8/27 10:13

打表程序(暴力)不知道为啥错了,找人帮忙。

#include<bits/stdc++.h>
using namespace std;
long long prime[1001],zhi[1001],num,l[1001],k[1001][1001],ans,anss[1001][1001],minn=100000000,m,t;
void dfs(long long x,long long y,long long n)
{
	if(x>n)
	{
		t=1;
		int ans=0;
		for(int i=1;i<=n;i++)	ans=ans+k[i][1]+k[1][i];//计算第一行第一列的和 
		ans=ans-k[1][1];
		if(ans<minn)//更新答案 
		{
			minn=ans;
			for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){anss[i][j]=k[i][j];};
		}
		return;
	}
	for(int i=2;i<=n*n;i++)
	{
		if(l[i]==1)	continue;//被用过的数跳过 
		if(l[i]==0)
		{
			if(x==1&&y==1)//好像不需要 
			{
				k[x][y]=i;
				l[i]=1;
				if(y==n)	dfs(x+1,1,n);
				else dfs(x,1+y,n);
				l[i]=0;	
				k[x][y]=0;
			} 
			if(x==1&&y!=1)//最左边的格子只收到上面的数影响 
			{
				if(prime[i+k[x][y-1]]==0)
				{
					k[x][y]=i;
					l[i]=1;
					if(y==n)dfs(x+1,1,n);
					else dfs(x,y+1,n);
					l[i]=0;
					k[x][y]=0;
				}
			}
			if(x!=1&&y==1)//最上面的只受左面的影响 
			{	
				if(prime[i+k[x-1][y]]==0)
				{
					k[x][y]==i;
					l[i]=1;
					if(y==n)	dfs(x+1,1,n);
					else dfs(x,y+1,n);
					l[i]=0;	
					k[x][y]=0;
				} 
			}
			if(x!=1&&y!=1)//受到上面和左面的影响 
			{
				if(prime[i+k[x-1][y]]==0&&prime[i+k[x][y-1]]==0)
				{
					k[x][y]==i;
					l[i]=1;
					if(y==n)	dfs(x+1,1,n); 
					else dfs(x,y+1,n);
					l[i]=0;	
					k[x][y]=0;
				} 
			}
		}
	}
	return ;
}
int main()
{
	int n;
	cin>>m;
	prime[1]=1; 
	for(int i=2;i<=1001;i++)//zhi[i]表示第i个质数为zhi[i],prime[i]用于判断i是否为质数 ,0代表是,1代表不是 
	{
		if(prime[i]==0)
		{
			num++;
			zhi[num]=i;
		}
		for(int j=1;j<=num&&i*zhi[j]<=1001;j++)
		{
			prime[i*zhi[j]]=1;
			if(i%zhi[j]==0)	break;
		}
	}
//	for(int i=1;i<=num;i++)	cout<<prime[i]<<" ";线性筛	
	k[1][1]=1;//左上角为1 
	l[1]=1;
	dfs(1,2,m);
	if(t==0)	cout<<"NO";//输出 
	else
	{
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cout<<anss[i][j]<<" ";
			}
			cout<<endl;
		}
	}
}
2020/8/27 10:13
加载中...