【基础题】蛇形填数

题目描述

在n*n方陈里填入1,2,...,n*n,要求填成蛇形。例如n=4时方陈为：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4

输入

直接输入方阵的维数，即n的值。(n<=100)

输出

输出结果是蛇形方陈。

样例输入

3

样例输出

7 8 1
6 9 2
5 4 3

先说一下我的思路，
我把n=4时的情况列了出来，发现了奇数时，j变化，偶数时，i变化等变化规律，后来我发现需要总结很多变化规律才能算数来，总结出了n=4的，n=5时又不一样了，哎，头疼（小白的思路。。）
大神们的思路：
①
这是个4连通问题。
针对每个方阵中的格子，与它四连通相邻的格子有4个：左右和上下；
要想访问它们有四个方向：向下y坐标加1，纵坐标加0，记为(0,1)，顺时针是向左(-1,0)，然后是(0,-1)，最后是(1,0)；可用一个方向数组存储这四个方向，切换时按顺序选取。
数组开设好，填充为0值；
种子格子为数组右上方元素填入第一个计数1，下面第一方向为(0,1)，按照这个方向如果发现新格子在数组坐标内且其值为0，则进行填充，再按照方向继续填充；
如果发现上面条件不满足换第二个方向(-1,0)继续填充；
直到当前格子的四个方向均不满足填充条件时结束。
这样得到的就是所谓蛇形填数的结果，而且与方阵尺寸无关。

②这个方法比较容易理解而且也简单不过只能对这个题：
数组开设好，填充0，遍历先右下，再左，再左上，再右。遍历过的设为1，即能实现蛇形遍历。

核心代码：

while (val<n*n)  
    {  
        while (x+1<n && !a[x+1][y])   a[++x][y]=++val;  
        while (y-1>=0 && !a[x][y-1])  a[x][--y]=++val;  
        while (x-1>=0 && !a[x-1][y])  a[--x][y]=++val;  
        while (y+1<n && !a[x][y+1])   a[x][++y]=++val;  
    }  

完整代码如下：

#include <cstdio>  
#include <cstring>  
#define MAXN 10  
int a[MAXN][MAXN];  
int main()  
{  
    int n, x, y, val=0;  
    scanf("%d",&n);  
    memset(a,0,sizeof(a));// clear array  
    val=a[x=0][y=n-1]=1;// set the first element  
    while (val<n*n)  
    {  
        while (x+1<n && !a[x+1][y])   a[++x][y]=++val;  
        while (y-1>=0 && !a[x][y-1])  a[x][--y]=++val;  
        while (x-1>=0 && !a[x-1][y])  a[--x][y]=++val;  
        while (y+1<n && !a[x][y+1])   a[x][++y]=++val;  
    }  
    for (x=0; x<n; ++x)  
    {  
        for (y=0; y<n; ++y)  
        {  
            printf("%3d",a[x][y]);  
        }  
        printf("
");  
    }  
    return 0;  
}