洛谷 P6291 [eJOI2017]骆驼题解--zhengjun_C

题目传送门

思路

一看就是构造题，显然要分成若干块 5 × 5 5\times5 5×5 的小块，然后发现对于一个小块中，只有最中间的那格可以从别的小块中一步跳进来。

然后我们打一个爆搜，打出从当前小块的中间走到各个方向相邻的小块的方案。

这样就可以在小块间移动了。

由于我们需要把所有的点都绕一遍，那么显然是在 2 ∼ N 5 2\sim \frac{N}{5} 2∼5N 行上边绕来绕去，直到最后一列绕完之后从第一行绕回第一格。

所以在 N N N 为奇数的时候，最后上去的时候需要把两列一起处理掉，然后就爆搜跑一个 5 × 10 5\times10 5×10 绕一遍的解（从 ( 3 , 3 ) (3,3) (3,3) 开始走最后走到 ( 3 , 1 ) (3,1) (3,1)），然后输出即可，注意特判 N = 5 N=5 N=5 和 N = 15 N=15 N=15 的点。

代码

#include
using namespace std;
int n;
int st[11][11]={
	{ 1,13,16, 0,12},
	{ 9, 4,23,20, 7},
	{15,18,11,14,17},
	{ 2,21, 8, 3,22},
	{10, 5,24,19, 6},
};
int ed[11][11]={
	{21,15, 5,20,14},
	{10,18,23,11, 3},
	{25, 7, 1,16, 6},
	{22,12, 4,19,13},
	{ 9,17,24, 8, 2},
};
int corner[11][11]={
	{28,41,50,27,42,18,24, 5,17,10},
	{38,21,30,39,13,46,32,12,45, 7},
	{49,35, 1,19,34,26,43, 9,25, 4},
	{29,40,14,22,31,15,23, 6,16,11},
	{37,20,48,36, 2,47,33, 3,44, 8},
};
int down[11][11]={
	{18,13, 5,19,14},
	{10,21,16,11, 3},
	{24, 7, 1,23, 6},
	{17,12, 4,20,15},
	{ 9,22,25, 8, 2},
};
int r[11][11]={
	{10,16, 5,11,17},
	{21,13, 8,20, 3},
	{ 6,24, 1,15,25},
	{ 9,19, 4,12,18},
	{22,14, 7,23, 2},
};
int up[11][11]={
	{18,10,25,17,11},
	{ 5,21,13, 8, 3},
	{24,16, 1,23,15},
	{19, 9, 4,20,12},
	{ 6,22,14, 7, 2},
};
int l[11][11]={
	{21,15, 5,20,14},
	{10,18,23,11, 3},
	{25, 7, 1,16, 6},
	{22,12, 4,19,13},
	{ 9,17,24, 8, 2},
};
int tmp[11][11]={
	{19,45,40,18,46,41,15, 5,30,10},
	{38,22,48,43,13,26,32,12,27, 7},
	{50,35, 1,24,34,17,29, 9,16, 4},
	{20,44,39,21,47,42,14, 6,31,11},
	{37,23,49,36, 2,25,33, 3,28, 8},
};
int ans[5001][5001];
void copy(int x,int y,const int (*a)[11],int n,int m,int st){
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans[(x-1)*5+i][(y-1)*5+j]=a[i-1][j-1]+st-1;
}
int main(){
	cin>>n;
	if(n%10==0){
		copy(1,1,st,5,5,1);ans[1][4]=n*n;
		int m=n/5,now=25;
		for(int i=1;i<=m;i++){
			if(i&1){
				for(int j=2;j<m;j++)copy(j,i,down,5,5,now),now+=25;
				copy(m,i,r,5,5,now);now+=25;
			}
			else if(i!=m){
				for(int j=m;j>2;j--)copy(j,i,up,5,5,now),now+=25;
				copy(2,i,r,5,5,now);now+=25;
			}
			else{
				for(int j=m;j>1;j--)copy(j,i,up,5,5,now),now+=25;
			}
		}
		for(int i=m;i>2;i--)copy(1,i,l,5,5,now),now+=25;
		copy(1,2,ed,5,5,now);now+=25;
	}
	else if(n==5){
		puts("1 14 7 4 15\n\
9 22 17 12 23\n\
19 5 25 20 6\n\
2 13 8 3 16\n\
10 21 18 11 24");
		return 0;
	}
	else{
		copy(1,1,st,5,5,1);ans[1][4]=n*n;
		int m=n/5,now=25;
		for(int i=1;i<m-1;i++){
			if(i&1){
				for(int j=2;j<m;j++)copy(j,i,down,5,5,now),now+=25;
				copy(m,i,r,5,5,now);now+=25;
			}
			else if(i!=m){
				for(int j=m;j>2;j--)copy(j,i,up,5,5,now),now+=25;
				copy(2,i,r,5,5,now);now+=25;
			}
			else{
				for(int j=m;j>1;j--)copy(j,i,up,5,5,now),now+=25;
			}
		}
		for(int i=m;i>=2;i--)copy(i,m-1,corner,5,10,now),now+=50;
		copy(1,m-1,tmp,5,10,now),now+=50;
		for(int i=m-2;i>2;i--)copy(1,i,l,5,5,now),now+=25;
		if(m>3)copy(1,2,ed,5,5,now);now+=25;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			printf("%d%c",ans[i][j],"\n "[j<n]);
		}
	}
	return 0;
}