记录编号	457693	评测结果	AAAAAAAAAA
题目名称	填数	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	1.381 s
提交时间	2017-10-09 09:33:04	内存使用	2.87 MiB

#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <cmath>
#include <deque>
#include <cstdlib>

using namespace std;

int book[400], n, isPrime[400], mmap[14][14], q, flag = 1;
vector<int> prime(0);
void Prime()
{
    int m = sqrt(250.5), i;
    for(i = 2; i <= m; i++)
    {
        if(!isPrime[i])
        {
            for(int j = i * i; j <= 250; j += i)
            {
                isPrime[j] = 1;
            }
        }
    }
    for(i = 2; i <= 250; i++)
    {
        if(!isPrime[i])
        {
            prime.push_back(i);
        }
    }
    return;
}
void dfs(int x, int y)
{
	int i, j = 0;
    if(y == n)
    {
        if(x == n)
        {
            for(i = 1; i <= n; i++)
            {
                for(j = 1; j <= n; j++)
                {
                    printf("%d ", mmap[i][j]);
                }
                printf("\n");
            }
            flag = 0;
            exit(0);
        }
        y = 1;
        x++;
        int w = mmap[x-1][y];
        while(prime[j] <= w)
        {
            j++;
        }
        for( ; j < prime.size(); j++)
        {
            int c = prime[j] - w;
			if(c > q)
			{
				break;
			}
            if(!book[c])
            {
                book[c] = 1;
                mmap[x][y] = c;
                dfs(x, y);
                book[c] = 0;
                mmap[x][y] = 0;
            }
        }
    }
    else
    {
        int w = mmap[x][y];
        y++;
        while(prime[j] <= w)
        {
            j++;
        }
        for( ; j < prime.size(); j++)
        {
            int c = prime[j] - w;
			if(c > q)
			{
				break;
			}
            if(!book[c])
            {
                if(!isPrime[c+mmap[x-1][y]]||!mmap[x-1][y])
                {
                    book[c] = 1;
                    mmap[x][y] = c;
                    dfs(x, y);
                    book[c] = 0;
                    mmap[x][y] = 0;
                }
            }
        }
    }
    return;
}
int main()
{
    freopen("tianshu.in", "r", stdin);
    freopen("tianshu.out", "w", stdout);

	scanf("%d", &n);

	if(n == 1)
    {
        printf("NO\n");
        return 0;
    }
	q = n * n;
	Prime();
	mmap[1][1] = 1;
	book[1] = 1;
	dfs(1, 1);
	if(flag)
    {
        printf("NO\n");
    }
	return 0;
}