记录编号	605488	评测结果	AAAAAAAAAA
题目名称	101.填数	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	1.955 s
提交时间	2025-09-02 19:36:55	内存使用	3.65 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int a[15][15],p[255];
bool isp[255],vis[255];
bool prime(int x)
{
    if(n==1) return false;
    for(int i=2;i*i<=x;i++) if(x%i==0) return false;
    return true;
}
bool dfs(int x,int y)
{
    if(x==n+1) return true;
    int t=max(a[x-1][y],a[x][y-1]);
    for(int j=1;j<=m;j++)
    {
        if(p[j]<=t) continue;
        int i=p[j]-t;
        if(i>n*n) break;
        if(vis[i]) continue;
        if(x!=1&&!isp[i+a[x-1][y]]) continue;
        if(y!=1&&!isp[i+a[x][y-1]]) continue;
        a[x][y]=i,vis[i]=1;
        if(y<n) if(dfs(x,y+1)) return true;
        if(y==n) if(dfs(x+1,1)) return true;
        a[x][y]=0,vis[i]=0;
    }
    return false;
}
int main()
{
    freopen("tianshu.in","r",stdin);
    freopen("tianshu.out","w",stdout);
    
    cin>>n;
    for(int i=1;i<=2*n*n-1;i++) if(isp[i]=prime(i)) p[++m]=i;
    a[1][1]=1,vis[1]=1;
    bool res=dfs(1,2);
    if(!res) cout<<"NO"<<endl;
    else
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++) cout<<a[i][j]<<' ';
            cout<<endl;
        }
    }
    return 0;
}