「EJOI2017」-骆驼

第一道构造题祭……

文字叙述：

题目的提示很明显。

$N$是$5$的倍数,所以考虑分成$5 \times 5$小块连在一起。

首先通过打表证明，

小块里从任何一点出发，经过所有的格，从任一一点跳出，一定有这样的路径。

那么因为此题$spj$，所以只要想方设法构造出一种可行解就$OK$辣。

所以我们把大的棋盘分成很多小块，并把小块连在一起。

要分奇偶连接。

在连接时要尽量横竖移动，这样优化代码复杂度。

给出我的连接方案：

当然，你这样连也是可以的（加油）：

我们给一个小块内的格设置一个连通参数，即一步可以跳到的其他块数。

有：

发现如果选择$(3,3)$点会很优。

于是……（学会偷懒，写函数！）

我们把向四个方向的块，奇数起点，奇数起点右下点，偶数起点预处理（共$7$个）

如果想要更清楚的往下看：

偶数的起点：

最后从右面返回。

奇数的起点和右下的终点接口：

向右走（左面的块方向定义为向右）「向左同理」：

向下走（上面的块方向定义为向下）「向上同理」：

码一下就好了～～

#include <iostream>

#include <cstring>

#include <cstdio>

#define L 1111

#define N 222

#define JST 0

#define JJK 1

#define OST 2

#define DOWN 3

#define UP 4

#define LEFT 5

#define RIGHT 6

using namespace std;

const int stdsq[7][5][5]={

	{

		{ 1, 8,16, 2, 7},

		{11,19, 5,10,18},

		{22,14, 0,21,15},

		{ 4, 9,17, 3, 6},

		{12,20,23,13, 0}

	},

	{

		{22, 3, 9,23, 2},

		{16,25,20,17, 7},

		{10,13, 1, 4,12},

		{21,18, 8,24,19},

		{15, 5,11,14, 6}

	},

	{

		{ 1,12, 5, 2,13},

		{ 7,18,15,10,19},

		{23, 3, 0,22, 4},

		{16,11, 6,17,14},

		{ 8,21,24, 9,20}

	},

	{

		{ 6,22,14, 7, 2},

		{19, 9, 4,20,12},

		{24,16, 1,23,15},

		{ 5,21,13, 8, 3},

		{18,10,25,17,11}

	},

	{

		{ 9,22,25, 8, 2},

		{17,12, 4,20,15},

		{24, 7, 1,23, 6},

		{10,21,16,11, 3},

		{18,13, 5,19,14}

	},

	{

		{ 9,17,24, 8, 2},

		{22,12, 4,19,13},

		{25, 7, 1,16, 6},

		{10,18,23,11, 3},

		{21,15, 5,20,14}

	},

	{

		{22,14, 7,23, 2},

		{ 9,19, 4,12,18},

		{ 6,24, 1,15,25},

		{21,13, 8,20, 3},

		{10,16, 5,11,17}

	}

};

int ans[L][L],len,bn;

struct Fivesq{

	int id,addup;

	void update(const int x,const int y){

		for(int i=0;i<5;i++)

			for(int j=0;j<5;j++)

				ans[x+i][y+j]=stdsq[id][i][j]+addup;

	}

};

Fivesq mp[N][N];

void set(int li,int f,int t,int val){

	for(int i=f;i<=t;i++)

		mp[li][i].id=val;

}

void search(int x,int y,const int lsv){

	int val=lsv;

	while(mp[x][y].id!=JST \

			&&mp[x][y].id!=JJK \

				&&mp[x][y].id!=OST){

				//cout<<x<<" "<<y<<" "<<mp[x][y].id<<endl;

		mp[x][y].addup=val;

		val+=25;

		if(mp[x][y].id==UP   )x--;

		else if(mp[x][y].id==DOWN )x++;

		else if(mp[x][y].id==LEFT )y--;

		else if(mp[x][y].id==RIGHT)y++;

	}

	if(mp[x][y].id==JJK){

		mp[x][y].addup=val;

	}

}

int main(){

	scanf("%d",&len);

	if(len==5){

		puts("1 14 7 4 15\n9 22 17 12 23 \n19 5 25 20 6\n2 13 8 3 16 \n10 21 18 11 24");

		return 0;

	}

	bn=len/5;

	if(bn&1){

		mp[0][0].id=JST;

		mp[1][1].id=JJK;

		for(int i=1;i<bn;i++){

			if(i&1)mp[0][i].id=DOWN;

			else   mp[0][i].id=LEFT;

		}

		for(int i=2;i<bn;i++){

			if(i&1)mp[1][i].id=LEFT;

			else   mp[1][i].id=UP;

		}

		for(int i=1;i<bn;i++)

			mp[i][0].id=DOWN;

		mp[bn-1][0].id=RIGHT;

		for(int i=2;i<bn;i++){

			if(i&1){

				set(i,1,bn-1,LEFT);

				mp[i][1].id=UP;

			}

			else{

				set(i,1,bn-1,RIGHT);

				mp[i][bn-1].id=UP;

			}

		}

		search(1,0,23);

		for(int i=0;i<bn;i++)

			for(int j=0;j<bn;j++)

				mp[i][j].update(i*5,j*5);

		ans[2][2]=len*len;

		ans[4][4]=len*len-1;

	}

	else{

		mp[0][0].id=OST;

		for(int i=1;i<bn;i++)

			mp[i][0].id=DOWN;

		mp[bn-1][0].id=RIGHT;

		set(0,1,bn-1,LEFT);

		for(int i=1;i<bn;i++){

			if(i&1){

				set(i,1,bn-1,RIGHT);

				mp[i][bn-1].id=UP;

			}

			else{

				set(i,1,bn-1,LEFT);

				mp[i][1].id=UP;

			}

		}

		/*for(int i=0;i<bn;i++){

			for(int j=0;j<bn;j++){

				printf("%d ",mp[i][j].id);

			}puts("");

		}*/

		search(1,0,24);

		for(int i=0;i<bn;i++)

			for(int j=0;j<bn;j++)

				mp[i][j].update(i*5,j*5);

		ans[2][2]=len*len;

	}

	for(int i=0;i<len;i++){

		for(int j=0;j<len;j++){

			printf("%d ",ans[i][j]);

		}puts("");

	}

}

巴特西