P6291 [eJOI2017]骆驼 题解

· · 题解

满分做法： 令 $ 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;
}