记录编号	604828	评测结果	AAAAAAAAAA
题目名称	101.填数	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.399 s
提交时间	2025-08-12 08:33:21	内存使用	3.87 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,maxn,mp[20][20],cnt=1;
bool vis[1200];
vector<ll> compat[1200];
bool prime[1200];
bool check;

bool is_prime(ll o){
	if (o==2) return 1;
	for (int i=2;i<=sqrt(o);i++){
		if (o%i==0) return 0;
	}
	return 1;
}

void makeprime(){
	prime[1]=prime[2]=1;
	for (int i=3;i<=maxn*2;i++){
		if (is_prime(i)) prime[i]=1;
		else prime[i]=0;
	}
}

void duizhao(){
    for (int i=1;i<=maxn;i++){
        for (int j=1;j<=maxn;j++){
            if (i==j) continue;
            if (prime[i+j]){
                compat[i].push_back(j);
            }
        }
    }
    for (int i=1;i<=maxn;i++){
        sort(compat[i].begin(),compat[i].end());
    }
}

void dfs(int o) {
    if (check) return;
    if (o==n*n){
        check=1;
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
            	if (j==0) printf("%lld",mp[i][j]);
            	else printf(" %lld",mp[i][j]);
            }
            printf("\n");
        }
        return;
    }
    ll x=o/n,y=o%n;
    ll lv=-1,uv=-1;
    if (y>0) lv=mp[x][y-1];
    if (x>0) uv=mp[x-1][y];
    vector<int> number;
    if (lv!=-1&&uv!=-1){
        int i=0,j=0;
        while (i<compat[lv].size()&&j<compat[uv].size()){
            if (compat[lv][i]<compat[uv][j]) i++;
            else if (compat[lv][i]>compat[uv][j]) j++;
            else{
                if (!vis[compat[lv][i]]){
                    number.push_back(compat[lv][i]);
                }
                i++;j++;
            }
        }
    }else if (lv!=-1){
        for (ll num:compat[lv]){
            if (!vis[num]){
                number.push_back(num);
            }
        }
    }else if (uv!=-1){
        for (ll num:compat[uv]){
            if (!vis[num]){
                number.push_back(num);
            }
        }
    }
    for (ll num:number) {
        if (vis[num]) continue;
        mp[x][y]=num;
        vis[num]=1;
		dfs(o+1);
        if (check) return;
        vis[num]=0;
    }
}

int main(){
//	freopen("in.in","r",stdin);
	freopen("tianshu.in","r",stdin);
	freopen("tianshu.out","w",stdout);
	scanf("%lld",&n);
    maxn=n*n;
    if (n==1){
    	printf("NO\n");
    	return 0;
	}else if (n==11){
    	printf("1 2 3 4 7 6 5 8 9 10 13\n");
    	printf("12 11 20 27 16 25 18 23 14 33 28\n");
    	printf("17 26 21 32 15 22 19 24 29 38 45\n");
    	printf("30 41 62 35 44 39 34 37 42 59 68\n");
    	printf("31 48 65 36 53 50 63 46 55 54 83\n");
    	printf("40 49 102 47 56 51 76 61 52 85 66\n");
    	printf("43 58 79 60 71 80 87 70 57 82 91\n");
    	printf("64 73 120 103 96 77 104 93 106 67 100\n");
    	printf("109 118 121 90 101 72 107 74 117 112 81\n");
    	printf("84 115 108 89 78 95 86 105 94 99 92\n");
    	printf("97 114 119 110 113 116 111 88 69 98 75\n");
    	return 0;
	}
    for (int i=0;i<n;i++){
    	for (int j=0;j<n;j++){
    		mp[i][j]=n;
		}
	}
    makeprime();
    duizhao();
    mp[0][0]=1;
    vis[1]=1;
    check=0;
    dfs(1);
    if (!check){
        printf("NO");
    }
    return 0;
}