题目描述
在N imes NN×N的棋盘上(1≤N≤10)(1≤N≤10)，填入1,2,…,N^21,2,…,N2共N^2N2个数，使得任意两个相邻的数之和为素数。
例如：当N=2N=2时，有： 
其相邻数的和为素数的有：
1+2,1+4,4+3,2+31+2,1+4,4+3,2+3
当N=4N=4时，一种可以填写的方案如下： 
在这里我们约定：左上角的格子里必须填数字11。
输入输出格式
输入格式：
一个数NN
输出格式：
如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO”。
输入输出样例
输出样例#2：
1 2 4 3
过了初赛，感觉还行
不知道为什么突然犯病写了97年的远古题目，而且还调了一天
数据是10的显而易见的爆搜加优化，然而死活过不了
思路一：
枚举每个数放在那个位置
只有80pts
代码：
#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> using namespace std; inline int rd(){ int f=1,x=0; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,i,j,k; int map[11][11],book[11][11],ans[11][11],minn=99999999,f=0; int p[10006]; int pos=0,pri[10006]; void pre(){ int m=2*n*n; p[1]=1; for(int i=2;i<=m;i++){ if(!p[i]) pri[++pos]=i; for(int j=1;j<=pos;j++){ if(pri[j]*i>m) break; p[i*pri[j]]=1; if(i%pri[j]==0) break; } } return ; } int sum=0; void print(){ if(sum<minn){ f=1; minn=sum; memcpy(ans,map,sizeof(ans)); } return ; } int check(int x,int y,int a){ if(book[x-1][y]&&p[map[x-1][y]+a]) return 0; if(book[x+1][y]&&p[map[x+1][y]+a]) return 0; if(book[x][y-1]&&p[map[x][y-1]+a]) return 0; if(book[x][y+1]&&p[map[x][y+1]+a]) return 0; return 1; } void dfs(int x) { if(x==n*n+1){ /*for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d",map[i][j]); if(j!=n) putchar(' '); } puts(""); }*/ print(); return ; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(!book[i][j]){ if(check(i,j,x)){ if(i==1||j==1) sum+=x; map[i][j]=x; book[i][j]=1; dfs(x+1); book[i][j]=0; if(i==1||j==1) sum-=x; } } } } return ; } int main() { n=rd(); pre(); map[1][1]=1; book[1][1]=1; if(n==1){ printf("NO"); return 0; } dfs(2); if(f){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d",ans[i][j]); if(j!=n) putchar(' '); } puts(""); } } else printf("NO"); return 0; }
思路二：
枚举每个位置放哪个数
优化方法，从左上到右下
尽量让第一行和第一列的数最小
所以别的地方的尽量大
下面给出代码：
#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> using namespace std; inline int rd(){ int f=1,x=0; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n,i,j,k; int map[11][11],book[11][11],ans[11][11],minn=99999999,f=0; int p[10006]; int pos=0,pri[10006]; int vis[10006]; void pre(){ int m=2*n*n; p[1]=1; for(int i=2;i<=m;i++){ if(!p[i]) pri[++pos]=i; for(int j=1;j<=pos;j++){ if(pri[j]*i>m) break; p[i*pri[j]]=1; if(i%pri[j]==0) break; } } return ; } void print(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ write(map[i][j]); putchar(' '); } puts(""); } return ; } int check(int x,int y,int a){ if(x>1&&book[x-1][y]&&p[map[x-1][y]+a]) return 0; if(x<n&&book[x+1][y]&&p[map[x+1][y]+a]) return 0; if(y>1&&book[x][y-1]&&p[map[x][y-1]+a]) return 0; if(y<n&&book[x][y+1]&&p[map[x][y+1]+a]) return 0; return 1; } void dfs(int x,int y){ if(x==n+1&&y==1){ print(); exit(0); } int m=n*n; if(x==1||y==1){ for(int i=2;i<=m;i++){ if(!vis[i]){ if(check(x,y,i)){ vis[i]=1; map[x][y]=i; book[x][y]=1; if(y==n) dfs(x+1,1); else dfs(x,y+1); vis[i]=0; book[x][y]=0; map[x][y]=0; } } } } else{ for(int i=m;i>=2;i--){ if(!vis[i]){ if(check(x,y,i)){ book[x][y]=1; vis[i]=1; map[x][y]=i; if(y==n) dfs(x+1,1); else dfs(x,y+1); vis[i]=0; book[x][y]=0; map[x][y]=0; } } } } } int main() { n=rd(); pre(); map[1][1]=1; book[1][1]=1; vis[1]=1; if(n==1){ printf("NO"); return 0; } dfs(1,2); printf("NO"); return 0; }