记录编号	604761	评测结果	ATAWTTTTTA
题目名称	101.填数	最终得分	30
用户昵称	汐汐很希希	是否通过	未通过
代码语言	C++	运行时间	18.007 s
提交时间	2025-08-11 17:39:09	内存使用	3.46 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[15][15],vis[150],ans[15][15],sum[15];
bool flag=false;
bool prime(int x)
{
    for(int i=2;i*i<=x;i++) if(x%i==0) return false;
    return true;
}
bool pd(int x,int y)
{
    if(!prime(a[x][y]+a[x-1][y])&&a[x-1][y]!=0) return false;
    if(!prime(a[x][y]+a[x][y-1])&&a[x][y-1]!=0) return false;
    if(!prime(a[x][y]+a[x+1][y])&&a[x+1][y]!=0) return false;
    if(!prime(a[x][y]+a[x][y+1])&&a[x][y+1]!=0) return false;
    return true;
}
void dfs(int t,int x,int y,int cnt)
{
    if(t==n*n+1&&cnt==0)
    {
        flag=true;
        bool sw=false,t=true;
        int sum1=0;
        for(int i=1;i<=n;i++){
            if(t){
                for(int j=1;j<=n;j++) sum1+=a[i][j];
                if(sum1<sum[i]) sw=true,t=false;
                else if(sum1>sum[i]) t=false;
                sum1=0;
            }
        }
        if(sw)
        {
            memset(sum,0,sizeof(sum));
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=a[i][j];
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) sum[i]+=a[i][j];
        }
        return;
    }
    for(int i=2;i<=n*n;i++)
    {
        if(vis[i]!=0) continue;
        a[x][y]=i;
        if(pd(x,y)){
            vis[i]=1;
            if(y+1>n) dfs(t+1,x+1,1,cnt-1);
            else dfs(t+1,x,y+1,cnt-1);
        }
        a[x][y]=0;
        vis[i]=0;
    }
    return;
}
int main()
{
    freopen("tianshu.in","r",stdin);
    freopen("tianshu.out","w",stdout);
    
    cin>>n;
    memset(sum,0x3f,sizeof(sum));
    a[1][1]=1,vis[1]=1;
    if(n==1){
        cout<<"NO"<<endl;
        return 0;
    }
    dfs(2,1,2,n*n-1);
    if(!flag) cout<<"NO"<<endl;
    else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cout<<ans[i][j]<<' ';
            cout<<endl;
        }
    }
    return 0; 
}