题解 P5731 【【深基5.习6】蛇形方阵】

· · 题解

这道题我感觉不是红题

思路

思路感觉还是比较好想的。

从 1 到 n^2 依次算。先往右，走到头往下，再走到头往左，以此类推。

那为啥我说这道题不止红题呢？主要是实现很麻烦。

实现

主要问题是怎么转。其实每次转都相当于是往右转，所以只需要定义一个改变位置的数组，还有一个变量记录现在头朝哪边，每次转改变一下就行了。注意不能直接改，需要 %4。

如果不好理解，看一下代码。

改变位置的数组：

int pos[4][2]={0,1,1,0,0,-1,-1,0};//0表示右，1表示下，2表示左，3表示上

核心代码：

//a记录输出，d记录头朝向（含义同pos）
int tx=x+pos[d][0],ty=y+pos[d][1];//先变着
if(tx<1||tx>n||ty<1||ty>n||a[tx][ty])//如果越界或以前填过
    d=(d+1)%4;//头往右转，注意%4
x+=pos[d][0],y+=pos[d][1];//改变x和y

当然还有一些细节，比如输出要用%3d等。

代码

下面放完整代码——

（我知道你们只看这里）

#include<cstdio>
using namespace std;
int read(){//没啥用的快读
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[15][15];//记录输出的数组
int pos[4][2]={0,1,1,0,0,-1,-1,0};//改变位置的数组
int main(){//主函数
    int n=read(),x=1,y=1,d=0;//初始化
    for(int i=1;i<=n*n;i++){//遍历
        a[x][y]=i;//赋值
        int tx=x+pos[d][0],ty=y+pos[d][1];//核心代码，解释见上
        if(tx<1||tx>n||ty<1||ty>n||a[tx][ty]) d=(d+1)%4;
        x+=pos[d][0],y+=pos[d][1];
    }
    for(int i=1;i<=n;i++){//输出
        for(int j=1;j<=n;j++) printf("%3d",a[i][j]);//注意%3d
        if(i<n) printf("\n");
    }
    return 0;//华丽结束
}

看我这么晚还发题解，点个赞再走呀~