## 题解 P1549 【棋盘问题（2）】

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 13;
const int M = N * N;
const int K = M << 1;
int a[N][N], p[M][M], pr[K], L[M], P[M][M][M], PL[M][M], n, l, o;
bool v[K], vis[M], pi[M][M];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline void ri(int &x, int &y)
{
y++;
if (y > n)
{
y = 1;
x++;
}
}
inline void dw(int &x, int &y)
{
x++;
if (x > n)
x = y = 2;
}
bool dfs(int x, int y)
{
if (x > n)
return true;
int i, le = a[x][y - 1], u = a[x - 1][y], xx = x, yy = y, g;
if (!(x ^ 1) && y ^ 1)//搜第一行
{
ri(xx, yy);
for (i = 1; i <= L[le]; i++)
if (!vis[g = p[le][i]])
{
a[x][y] = g;
vis[g] = 1;
if (dfs(xx, yy))
return true;
vis[g] = 0;
a[x][y] = 0;
}
}
else
if (x ^ 1 && !(y ^ 1))//搜第一列
{
dw(xx, yy);
for (i = 1; i <= L[u]; i++)
if (!vis[g = p[u][i]])
{
a[x][y] = g;
vis[g] = 1;
if (dfs(xx, yy))
return true;
vis[g] = 0;
a[x][y] = 0;
}
}
else
{
ri(xx, yy);
if (!(yy ^ 1))
yy++;
if (rand() & 1)//随机数折中
for (i = PL[le][u]; i; i--)//从大到小搜
{
g = P[le][u][i];
if (!vis[g])
{
a[x][y] = g;
vis[g] = 1;
if (dfs(xx, yy))
return true;
vis[g] = 0;
a[x][y] = 0;
}
}
else
for (i = 1; i <= PL[le][u]; i++)//从小到大搜
{
g = P[le][u][i];
if (!vis[g])
{
a[x][y] = g;
vis[g] = 1;
if (dfs(xx, yy))
return true;
vis[g] = 0;
a[x][y] = 0;
}
}
}
return false;
}
int main()
{
srand(9982123);//仅本地能过，洛谷IDE无法过9的数据，不行还是上time(NULL)吧
int m, i, j, k, x;
n = re();
if (!(n ^ 1))//特判掉1
{
printf("NO");
return 0;
}
o = n * n;
m = o << 1;
v[0] = v[1] = 1;
for (i = 2; i <= m; i++)//线性筛素数
{
if (!v[i])
pr[++l] = i;
for (j = 1; j <= l; j++)
{
if (i * pr[j] > m)
break;
v[i * pr[j]] = 1;
if (!(i % pr[j]))
break;
}
}
for (i = 1; i < o; i++)
for (j = i + 1; j <= o; j++)//预处理每个数能和哪些数的和是素数
if (!v[i + j])
{
p[i][++L[i]] = j;
p[j][++L[j]] = i;
pi[i][j] = pi[j][i] = 1;
}
for (i = 1; i <= o; i++)
sort(p[i] + 1, p[i] + L[i] + 1);//排序
for (i = 1; i < o; i++)//预处理每两个数能和哪些数拼成素数
for (j = i + 1, m = L[i]; j <= o; j++)
for (k = 1; k <= m; k++)
if (pi[x = p[i][k]][j])
P[i][j][++PL[i][j]] = P[j][i][++PL[j][i]] = x;
a[1][1] = 1;
vis[1] = 1;
if (dfs(1, 2))
for (i = 1; i <= n; i++, printf("\n"))
for (j = 1; j <= n; j++)
printf("%d ", a[i][j]);
else
printf("NO");
return 0;
}