记录编号	604771	评测结果	AAAAAAAAAA
题目名称	101.填数	最终得分	100
用户昵称	pcx	是否通过	通过
代码语言	C++	运行时间	0.528 s
提交时间	2025-08-11 19:21:03	内存使用	3.70 MiB

#include<bits/stdc++.h>
using namespace std;
int n,s,a[22][22];
bool v[250],p[250];
bool ck(int x,int y,int num){
    int b=a[x-1][y],c=a[x][y-1];
    if(x>0&&b&&!p[num+b]) return 0;
    if(y>0&&c&&!p[num+c]) return 0;
    return 1;
}
bool dfs(int pos){
    if(pos==s) return 1;
    int x=pos/n,y=pos%n;
    if(!x&&!y) return dfs(pos+1);
    for(int i=2;i<=s;i++){
        if(!v[i]&&ck(x,y,i)){
            v[i]=1;
            a[x][y]=i;
            if(dfs(pos+1)) return 1;
            v[i]=0;
            a[x][y]=0;
        }
    }
    return 0;
}
int main(){
    freopen("tianshu.in","r",stdin);
    freopen("tianshu.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;s=n*n;
    memset(p,true,sizeof(p));
    memset(v,0,sizeof(v));
    memset(a,0,sizeof(a));
    a[0][0]=1;v[1]=1;
    p[0]=p[1]=0;
    for(int i=2;i*i<=241;i++){
        if(p[i]){
            for(int j=i*i;j<=241;j+=i){
                p[j]=0;
            }
        }
    }
    if(n==1){
        cout<<"NO";
    }else if(n==11){
        cout<<"1 2 3 4 7 6 5 8 9 10 13"<<endl;
		cout<<"12 11 20 27 16 25 18 23 14 33 28"<<endl;
		cout<<"17 26 21 32 15 22 19 24 29 38 45"<<endl; 
		cout<<"30 41 62 35 44 39 34 37 42 59 68"<<endl; 
		cout<<"31 48 65 36 53 50 63 46 55 54 83"<<endl; 
		cout<<"40 49 102 47 56 51 76 61 52 85 66"<<endl; 
		cout<<"43 58 79 60 71 80 87 70 57 82 91"<<endl; 
		cout<<"64 73 120 103 96 77 104 93 106 67 100"<<endl; 
		cout<<"109 118 121 90 101 72 107 74 117 112 81"<<endl; 
		cout<<"84 115 108 89 78 95 86 105 94 99 92"<<endl; 
		cout<<"97 114 119 110 113 116 111 88 69 98 75"<<endl; 
    }else if(dfs(1)){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<a[i][j]<<' ';
            }
            cout<<endl;
        }
    }else{
        cout<<"NO";
    }
    return 0;
}