自动搬运

查看原文

来自洛谷，原作者为

	bits。 菜的一批

搬运于2025-08-24 22:19:24，当前版本为作者最后更新于2020-06-02 13:55:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$20$ 分思路：爆搜即可。

满分做法：

令 $m = {n \over 5}$

一看 $n \leq 1000$ ，就知道搜索是会超时的。我们可以想到用构造矩阵的思想来解决这道题。题目说 $n$ 是 $5$ 的倍数，可以尝试构造 $5 \times 5$ 的矩阵拼合成答案矩阵来解决。

先假设能构造这样的 $5 \times 5$ 矩阵可以实现向上走，向左走，向右走，向下走，不妨来想这样一个问题：对于一个 $m \times m$ 的格子图，从坐标为 $(1,1)$ 的格子出发，每次可以向上，向左，向右，向下走，问怎么走才能不重不漏地走过每一个格子并最终回到起点。

当 $m$ 为偶数时，显然可以这样走（以 $m = 4$ 为例）：

（图略丑，不要见怪）

当 $m$ 为奇数时，如果只满足以上操作则无解，但如果可以从 $(2,2)$ 的格子直接到 $(1,1)$ 的格子，就可以满足（至于如何实现等一下会讲）（以 $m = 5$ 为例）：

接下来的问题就是如何构造 $5 \times 5$ 矩阵了。

我们可以发现，对于一个矩阵，它正中心的格子连接其内部格子的数量有四格，而其它仅有三格。所以我们可以以中心点为连接其它矩阵的进行转移，如下（红色为矩阵内部的起点，蓝色为终点，以向左和向上为例，向右和向下同理）：

对于 $m$ 为奇数，可以如下处理（绿色为中转点）：

对于 $m$ 为偶数，直接从右往左走即可：

至于如何在一个 $5 \times 5$ 的矩阵中做到，可以手玩（如果不想可以看代码）

#include <cstdio>
#include <cstdlib>
#define re register
#define xia 3
#define shang 4
#define zuo 5
#define you 6//意思是拼音
using namespace std;
const int MAXN=1e3+1;
const int mat[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}//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}
    }//向右
};//0、1矩阵处理奇数情况，2矩阵处理偶数情况
//以上为构造的矩阵
int n,nn;
int ans[MAXN][MAXN];
struct node{
	int id,add;
	inline void up(int x,int y){
		for(re int i=1;i<=5;i++)
			for(re int j=1;j<=5;j++)
				ans[i+x][j+y]=mat[id][i-1][j-1]+add;
	}//具体来算步数
}b[201][201];
inline void calc(int x,int y,int val){
	while(b[x][y].id && b[x][y].id!=1 && b[x][y].id!=2){
		b[x][y].add=val;
		val+=25;
		if(b[x][y].id==xia) x++;
		else if(b[x][y].id==shang) x--;
		else if(b[x][y].id==zuo) y--;
		else if(b[x][y].id==you) y++;
	}
	if(b[x][y].id==1) b[x][y].add=val;
}//算每个矩阵到达前的步数
int main(){
	scanf("%d",&n),nn=n/5;
	if(n==5)return 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"),0;//特判
	if(nn&1){
		b[1][1].id=0,b[2][2].id=1;
		for(re int i=2;i<=nn;i++){
			if(i&1) b[1][i].id=zuo;
			else b[1][i].id=xia;
		}
		for(re int i=3;i<=nn;i++){
			if(i&1) b[2][i].id=shang;
			else b[2][i].id=zuo;
		}
		for(re int i=2;i<nn;i++)
			b[i][1].id=xia;
		b[nn][1].id=you;
		for(re int i=3;i<=nn;i++)
			if(i&1){
				for(re int j=2;j<nn;j++)
					b[i][j].id=you;
				b[i][nn].id=shang;
			}else{
				for(re int j=3;j<=nn;j++)
					b[i][j].id=zuo;
				b[i][2].id=shang;
			}
		calc(2,1,23);//奇数有两个0，所以为25-2
	}
    else{
		b[1][1].id=2;
		for(re int i=2;i<nn;i++)
			b[i][1].id=xia;
		b[nn][1].id=you;
		for(re int i=2;i<=nn;i++)
			b[1][i].id=zuo;
		for(re int i=2;i<=nn;i++)
			if(i&1){
				for(re int j=3;j<=nn;j++)
					b[i][j].id=zuo;
				b[i][2].id=shang;
			}else{
				for(re int j=2;j<nn;j++)
					b[i][j].id=you;
				b[i][nn].id=shang;
			}
		calc(2,1,24);//偶数为25-1
	}
	for(re int i=1;i<=nn;i++)
		for(re int j=1;j<=nn;j++)
			b[i][j].up((i-1)*5,(j-1)*5);
	if(nn&1) ans[5][5]=n*n-1;
	ans[3][3]=n*n;
	for(re int i=1;i<=n;i++,puts(""))
		for(re int j=1;j<=n;j++){
			printf("%d ",ans[i][j]);
		}
	return 0;
}