题解

#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=x10+ch-'0';
return xf;
}
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=2nn;
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[ipri[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(xn+1&&y1){
print();
exit(0);
}
int m=n*n;
if(x1||y1){
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(yn) 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(yn) 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(n1){
printf("NO");
return 0;
}
dfs(1,2);
printf("NO");
return 0;
}